[java 백준] 골드 5/1107번 리모컨

https://www.acmicpc.net/problem/1107

1107번: 리모컨

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static int n;
    public static int m;
    public static int cnt;
 
    public static boolean broken[] = new boolean[10];
 
    public static int check(int n) {
        if (n == 0) {
            if (broken[0]) {
                return 0;
            } else {
                return 1;// 리모컨 한번 움직임
            }
        }
        int len = 0;// 리모컨 움직인 횟수
        while (n > 0) {
            if (broken[n % 10]) {
                return 0;
            }
            n /= 10;
            len++;
        }
        return len;
 
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        if (m != 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < m; i++) {
                int num = Integer.parseInt(st.nextToken());
                broken[num] = true;
            }
        }
 
        int minCnt = Math.abs(n - 100);
 
        for (int i = 0; i <= 1000000; i++) {
            int len = check(i);
            if (len > 0) {
 
                int press = Math.abs(n - i);// +와 -버튼 횟수
                minCnt = Math.min(minCnt, len + press);
            }
 
        }
 
        System.out.println(minCnt);
 
    }
}

 

이 문제는 입력받은 숫자가 들어올때 그때에 맞춰서 결과값을 내놓는게 아니라 0부터 ~1000000까지 경우의 수를 다 계산해서 해당하는 값을 DP처럼 꺼내 쓰는 방식이여서 어려웠다.. ㅜ

모든 경우의 수를 다 고려해줘야 했기에 완전탐색을 써야한다는 것을 실감할 수 있었다. 

 

풀이 해설

1
9
1 2 3 4 5 6 7 8 9

 

100에서 1까지 갈 수 있는 최소 경우의 수를 생각해봐야 한다. 우리가 쓸 수 있는 리모컨은 0 밖에 없다.

 

그러면 +랑 -만 가지고 100에서 1까지 가려면 총 99번이 소요된다.

근데 0을 이용해서 간다면 0을 누르고 여기서 + 해주면 1이 된다 그러니까 얘는 2번 소요된다.

이 생각을 코드로 옮겨보면

 

for (int i = 0; i <= 1000000; i++) {
            int len = check(i); // 리모컨 숫자로 바로 조정
 
            if (len > 0) {
 
                int press = Math.abs(n - i);// +나 -버튼 누르는 횟수
 
                minCnt = Math.min(minCnt, len + press);
            }
}
 

이렇게 옮길 수 있다. 앞에서 입력값에 맞춰서 결과값을 내놓는게 아닌 모든 경우의 수를 구하고 거기에 입력값에 해당하는걸 꺼내쓰라고 했는데 이게 무슨 말이나면

 

우리가 1까지 가려면 check(1)을 해서는 갈 수가 없다. 왜냐면 1번 리모컨은 고장났기 때문에 어차피 0을 반환한다.

그러면 check(0)을 이용할 수 있다.

check(0)을 하면 len은 1이다. 

 

그러면 press도 1이고

minCnt는 Math.min(99,2)이기 때문에 당연히 2가 된다. 

즉, 1이 망가져서 쓰질 못하니 0을 통해서 1을 가는 방법을 생각해야 한다.

이게 수가 커지고 많아지면 하나하나 생각하기 힘드니까 완전탐색으로 모든 경우의 수를 다 생각해주고 꺼내쓰는 것 같다.

 

++) for문을 1000000까지 돌려준 이유는 감소하는 경우를 생각해준것이다.

예를 들어 리모턴이 4,5가 망가졌고 490000까지 간다고 했을 때 100부터 가는 것보단

600000에서 2100000을 빼주는게 더 최소거리이기 때문이다.

 

++) null Pointer 에러

 

나같은 경우는 null pointer 에러가 떴는데 예를 들어 m이 0 일때

14124
0

이런 경우에 if(m!=0)을 해주고 stringTokenizer을 써줘야 에러가 뜨지 않았다. 

꼭 if문으로 조건을 설정해주는 것이 중요하다. 

 

참고 사이트

 

https://velog.io/@hammii/%EB%B0%B1%EC%A4%80-1107-%EB%A6%AC%EB%AA%A8%EC%BB%A8-java

[백준] 1107 - 리모컨 (java)

 

https://seol-limit.tistory.com/48

[Baekjoon] 백준 1107번 리모컨