[백준] Java 1107 리모컨

문제

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

알고리즘

브루트포스

풀이

일단 모든 경우의 수를 다 구해본다.

이동하려는 채널은 500,000까지다.

하지만 버튼을 누르는 최소값을 구하려고 하면 전체 값에서 최소 값을 찾아야 한다.

계산하기 쉽게 현재 채널 0번이라고 했을 때 50만까지 +로만 50만번 누르면 갈 수 있다. 이 값은 +의 최대값이다.

하지만 100만에서 50만까지 -만 눌러서 가는 방법도 있다.

이 안에서의 최소값이 무조건 정답이 된다.
만약 101만에서 -만 누른다면 무조건 +만 누르는 것보다 크기 때문에 볼 필요가 없다.

이렇게 전체 범위를 구했으면 그 안에서 최소 버튼을 누르는 경우만 구해주면 된다.

그 설명은 아래 소스 코드에 포함되어 있다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Main {

    static boolean[] broken = new boolean[10];

    public static void main(String[] args) throws IOException {

        Main main = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        // 초기값은 숫자버튼을 안누르고 +,- 버튼으로만 움직인 경우의 수로 해준다. (이게 최대값임)
        int answer = Math.abs(n - 100);

        // 고장난 버튼에는 true로 값 변경
        if (m > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < m; i++) {
                int i1 = Integer.parseInt(st.nextToken());
                broken[i1] = true;
            }
        }

        // 최대값까지 계산을 해준다.
        for (int i = 0; i <= 1000000; i++) {

            // 고장난 버튼이 있는지 확인하면서 없으면 숫자버튼을 몇개 눌러야 하는지 확인한다.
            int possible = main.possible(i);

            // possible 함수에서 0보다 크다는 것은 해당하는 숫자가 고장난 버튼이 하나도 없다는 것이다.
            if (possible > 0) {

                // 숫자로 이동한 버튼 개수 + 현재 숫자와 이동할 채널의 차이(+,-로 이동할 개수)
                int len = possible + Math.abs(i - n);
                answer = Math.min(answer, len);
            }
        }

        System.out.println(answer);

        // 1. 정답의 최대값을 설정해준다. 정답의 최대값은 +,-로만 이동하는 경우이다.
        // 2. 고장난 버튼을 확인하여서 최대 몇번 갈 수 있는지 확인한다.
        // 3. 고장난 버튼이 발견되면 종료되고 여태까지 이동한 횟수만 리턴해준다.
        // 4. 나머지 채널은 +,-만 이용해서 이동해야 하기 때문에 차이를 구해주고 리턴한다.
        // 5. 주어진 값이 크지 않기 때문에 모든 값을 다 구해준다. (백만까지)

    }

    // 해당 숫자를 몇번 눌러야 하는지. 또한 고장난 버튼이 있는지 확인하는 함수
    private int possible(int c) {

        if (c == 0) {
            if (broken[0]) {
                return 0;
            } else {
                return 1;
            }
        }

        int len = 0;
        while (c > 0) {

            // 브루트포스 방식으로 풀려고 하는 것이니까 해당하는 숫자로 이동이 가능한지 보는 것이다.
            // 만약 고장난 버튼 중 하나라도 있으면 이 채널로는 숫자만으로 이동이 불가능하니까 0을 리턴해 주는 것이다.
            if (broken[c % 10]) {
                return 0;
            } else {
                // 그게 아니라면 계속 한자리씩 고장난 버튼인지 확인한다.
                c /= 10;
                len++;
            }
        }

        return len;
    }

}