백준 1107번 리모컨

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class RemoteCon {
    static String N;
    static int M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = st.nextToken();
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        int[] errBt = new int[M];
        if(M != 0){
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++) {
                errBt[i] = Integer.parseInt(st.nextToken());
            }
        }
        int target = Integer.parseInt(N);
        int min = Integer.MAX_VALUE;
        for (int i = 0; i <= 999999; i++) {
            boolean err = false;
            String str = String.valueOf(i);
            int len = str.length();
            loop:for (int j = 0; j < str.length(); j++) {
                for (int k = 0; k < M; k++) {
                    if(str.charAt(j)-'0'==errBt[k]){
                        err = true;
                        break loop;
                    }
                }
            }
            if(!err){
                min = Math.min(Math.abs(target-i)+len,min);
            }
        }

        min = Math.min(Math.abs(target-100),min);
        System.out.println(min);

    }
}

문제 조건

1. 수빈이가 100번 채널에서부터 +,-로 target으로 이동하는 횟수
2. 고장난 번호를 피해 번호를 입력하고, +,-로 target까지 이동하는 횟수

1,2번 둘중 더 적은 횟수를 고른다.

풀이방법

📢 target이 500,000까지 가능하지만, 리모컨이 9만 남고, target이 0번일 경우 999,999번 이동 해야하므로 i의 범위를 0부터 999,999로 설정하는것이 핵심이다.

1. i를 0부터 하나씩 늘려가며 i가 고장난 번호를 가지고 있는지 확인한다.
2. 고장난 번호가 없다면, (target까지의 이동횟수 + i의 번호입력 횟수)의 최솟값을 완전탐색으로 구해준다.
3. 완전탐색으로 구해준 최솟값과 100번 부터 이동한 횟수의 최솟값을 비교하여 더 적은 횟수를 출력한다.

후기

target에서 가장 근처의 번호를 구하고, +,-로 이동하려 했는데,
target에서 가장 근처의 번호를 구한다는게 반례가 너무 많아서 구현하기 어려웠다.
이문제는 전부 완전탐색으로 최솟값을 구하는 문제였고,
완전탐색으로 구현시 어렵지 않게 풀 수 있었다.