[JAVA] 백준 1107 - 리모컨

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

1107번: 리모컨

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 이동하고자 하는 채널
        int M = Integer.parseInt(br.readLine());

        List<Integer> wrongBtns = new ArrayList<>();

        if(M>0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0; i<M; i++){
                wrongBtns.add(Integer.parseInt(st.nextToken()));
            }
        }

        int answer = Math.abs(100 - N); // -나 +로만 움직였을 때의 횟수로 초기화

        for (int i = 0; i <= 999999; i++) { // 채널이 최대 여섯자리수이므로 999999까지 모두 검사
            String str = String.valueOf(i);
            boolean wrong = false;
            for (int j = 0; j < str.length(); j++) { // 버튼 한자리 수 씩 검사
                if (wrongBtns.contains(str.charAt(j) - '0')) { // 고장난 버튼이라 못누른다면 넘어감
                    wrong = true;
                    break;
                }
            }
            if (wrong) continue;

            int cnt = str.length() + Math.abs(i - N); // 숫자 버튼 누른 횟수 + (+나 -)버튼 누른 횟수
            answer = Math.min(answer, cnt); 
        }
        System.out.println(answer);
    }
}

 

 

버튼을 누르는 경우의 수를 모두 다 따지는 브루트 포스 문제였다.

브루트포스로 안하면 매우 어려워질 것 같다.

 

채널 N이 최대 500,000개 까지 이므로 누르고자 하는 버튼들 i는 여섯자리수의 최대인 999999까지 돈다.

(만약 1~8 버튼이 모두 고장났을 때, 버튼 9만 누를 수 있다.)

 

누르고자 하는 버튼들 중에 고장난 버튼이 포함되면 불가능한 경우이므로 continue로 넘어간다.

고장난 버튼이 아닌 버튼들의 경우에는 숫자 버튼을 누른 횟수와 +나 - 버튼을 누른 횟수를 더해준다.

 

숫자 버튼을 누른 횟수는 i의 자리수로 표현할 수 있고,

+나 -버튼을 누른 횟수는 i와 채널 N의 차이로 표현할 수 있다.

 

 

answer는 버튼을 누르지 않고 오직 +나 -로만 움직였을 경우로 초기화해주고, 

고장난 버튼이 포함되지 않을 경우, 버튼 누르는 횟수를 계속 비교해 최솟값을 구한다.