[완전탐색, 백트래킹] 백준 1107번 리모컨 자바 풀이

BOJ 1107 리모콘 자바(java) 풀이

• 랭크 : 골드5
• 백준 1107 리모컨
  
  
  

문제 정리

1. 리모컨의 일부 숫자 버튼이 고장났다.
2. 리모컨에는 0~9까지의 숫자 버튼과ㅏ +, - 버튼이 있다
3. '+' 버튼은 +1된 채널, '-' 버튼은 -1된 채널로 이동한다.
4. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
5. 수빈이가 지금 이동하려고 하는 채널은 N이고, 고장난 버튼이 주어질 때, 채널 N으로 이동하기 위해 최소 몇번 버튼을 눌러야 하는지 구하시오
6. 이동하려는 채널 최대 500,000
7. 수빈이가 지금 보고 있는 채널은 100번
   
   
   

문제 접근

이 문제는 다음과 같은 사항을 고려하여야 합니다

1. 고장난 버튼 수가 없는 경우 -> 입력 받지 않음
2. 원하는 번호가 100번인 경우 -> 0 출력하고 종료
3. 100번 채널에서 +, - 버튼으로만 이동하는 경우 클릭 수
4. 모든 경우 클릭해보기

처음에는 자리수만 맞추어서 계산해봤지만 예외가 생겼습니다
예를들어 입력이 다음과 같을때 4자리수 경우만 계산하면 답이 안나옵니다.

999
1
9

-> 답 1000 누르고 -하는게 5로 가장 적음
but, 4자리수만 따지게 되면 5보다 더 큰수가 나온다

문제 풀이

최대 500,000 채널까지 있으므로 최대 6자리까지 모두 눌러봐야 합니다.
모든 경우를 따져주기 위해서 백트래킹 방식으로 최솟값을 찾아나갑니다.

1. for문을 돌며 10개의 버튼 중 누를 수 있는 버튼이면 누른다. 그리고 숫자를 덧붙인다.
2. 그 숫자를 만들기 위해 눌러야 하는 버튼수를 계산한다.
   버튼 수 = (원하는 채널 숫자와 누른 수의 차이) + 누른 버튼 횟수(누른 수의 길이이
3. 최솟값을 업데이트 한다.
4. 길이가 6보다 작은 동안은 계속 길이를 늘려가며 번호를 눌러본다.
   즉 999를 찾기 위해서 0부터 999,999까지 모두 눌러본다.
   
   
   

백준 리모컨 자바 코드