이게 전부 돌아가도 틀리다면 대체 뭐가 문제일까요 ㅠㅠ
1107번 - 리모컨
추가 예외입니다!
5
2
4 6
답 : 1
정리해주신 예외에는 "제외한 숫자들 사이에 목적지가 있는 경우"를 커버하는 TC가 없었습니다.
제가 정리한 경우의 수 입니다.
broken : 고장난 버튼의 수
dst(s) : s 에서 목적지까지 +1 또는 -1로만 이동했을 때 최소 거리
digit(i) : i까지 가기 위해서 누르는 버튼의 수
-------------------------------------------
- broken이 0일 때 :dst(100)와 digit 중 작은 값이 답
- broken이 10일 때 : dst(100)가 답
- broken이 9이고 0번 버튼만 쓸 수 있는 경우 : dst(100)와 '0으로 이동한 뒤 dst(0)'의 최소
- 고장나지 않은 버튼 중 제일 작은 수의 버튼이 목적지보다 큰 경우
- 고장나지 않은 버튼 중 제일 작은 수의 버튼이 목적지보다 작은 경우
위 처럼 모든 경우를 따져보지 않고 구하는 방법입니다.
본래 이것이 더 부르트포스 접근 방식에 더 부합하는 것 같습니다.
네이버에 백준1107로 검색하면 제일 위에 나오는 블로그에서는 아래와 같이 설명했습니다.
고장나지 않은 모든 버튼들을 조합해서 누르는 모든 경우에 대해서
(버튼을 누르는 수) + (버튼을 누른 뒤 목적지까지 +1/-1로 이동할 때 최소 거리)를 모두 구하고 이들의 최소값을 구한다.
@niklasjang 와.. 진짜 뽀뽀해드리고 싶다
감사합니다~~~~
댓글을 작성하려면 로그인해야 합니다.
Rose 5년 전 93
문제풀다 너무 고통스러워서 다른분들 고통받지 말라고 수작업으로 진행했습니다.
많은 도움 되길 바랍니다.
@gkfkagkfka12