백준 1107번
https://www.acmicpc.net/problem/1107
문제
수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.
입력
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.
출력
첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.
생각하기
처음 문제를 해결하려고 했던 방법은 입력받은 N을 문자열로 처리해서
하나씩 쪼개서 숫자를 조합하는 방식으로 계산하려고 했는데,
만들다 보니 테스트케이스상 반례가 너무 많아서 if문을 남발하게 됐다,
결국에 이 방법으로는 해결 불가라는 결론을 내렸고,
다른 분들의 코드를 참고할 수밖에 없었다.
나는 입력을 BufferedReader로 받았는데 코드를 완성하고 나서도 계속 오류가나는 것이었다.
알고 보니 NullPointer 오류가 나는 것이었는데,
M이 0일 경우를 생각해서 br.readLine()을 받지 않을 경우도 생각을 했었어야 했다.
그래서 M이 0이 아니면 list를 생성되도록 if문을 추가해주고 나서부터 정답처리가 되었다.
동작
이 문제를 해결하려면 부르트포스 (완전탐색)을 사용해야 문제를 해결 할수 있다.
처음에 min값을 먼저 구한다. 시작점인 100번 채널에서 N번호 까지의 차이값이다.
이후 반복문을 돌려서 탐색한다.
반복의 범위는 N이 50만 이지만 우리가 누를 수 있는 버튼의 숫자중 9가 있음을 감안해서 999999의 값을 넣었다.
이제 0부터 시작해서 999999까지의 반복을 한다.
가장 첫번째 num==0일 때
if(num == 0 && list.contains(num))
0부터 출발해서 0을 누를 수 없는 경우
0부터 출발 하지 않고, 100에서 출발 하므로 min값 유지
else if(num == 0 && !list.contains(num))
0부터 시작인데, 0을 누를 수 있는 경우
0을 누를 수 있는 경우, 0을 눌러서 count + 1;
이후 num이 0보다 클 경우
while(num > 0)
큰 값에서 0을 제외하며 계속 줄여가면서
숫자 버튼을 누를 수 있는 경우와 버튼을 누를 수 없는 경우를 생각해서
계산한다.
숫자 버튼을 누를 수 있는 경우는 숫자 버튼을 누를 때마다 count가 증가하게 된다.
만약 num 값의 %10 값에 해당하는 숫자 버튼을 누를 수 없는 경우는 그대로 count=0과 함께 return 하게 된다.
애초에 이 num으로 이동할 수 없기 때문에 + - 버튼만 이동한다 생각하고
N-i값이 된다.
이 반복에서 min으로 최솟값을 계속 갱신하면서
반복이 종료된 후 min값이 최솟값이 된다.
TMI
처음에 쉬울 줄 알았서 싱글벙글 했던 내 자신이 밉다
이 문제를 가지고 거의 7시간을 붙잡고 있을 줄 누가 알았겠냐..
코드
import java.util.*; import java.io.*; public class Main { static List<Integer> list = new ArrayList<>(); static int count; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int N = Integer.parseInt(br.readLine()); int M = Integer.parseInt(br.readLine()); if( M != 0) { st = new StringTokenizer(br.readLine()); while(M-- > 0) { list.add(Integer.parseInt(st.nextToken())); } } int min = Math.abs(N - 100); // 누를 수 있는 숫자 버튼이 없는 경우 // (오로지 + - 버튼만 눌러서 채널이동) if(M == 10) { System.out.println(min); } else { for(int i = 0; i <= 999999; i++) { remote_control(i); if(count > 0) { min = Math.min(min, Math.abs(N - i) + count); } } System.out.print(min); } } // End of main private static void remote_control(int num) { count = 0; if(num == 0 && list.contains(num)) { count = 0; return; } else if(num == 0 && !list.contains(num)) { count = 1; return; } while(num > 0) { if(list.contains(num % 10)) { count = 0; return; } else { count++; num /= 10; } } } // End of remote_control } // End of class
