[BOJ] 1107:리모컨

0. 문제

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

1107번: 리모컨

1. 문제분석

- 처음에는 맨 처음 숫자를 눌러 가장 가까운 채널로 이동해 +, - 버튼에 따라 목표지점에 도달하는 최단 거리만 구하면 된다고 생각해서 BFS로 쉽게 풀 수 있을 것이라 생각했다. 하지만, 가장 가까운 채널로 이동하기 위해 가장 가까운 채널을 구하는 방법이 꽤나 복잡해져서 포기했다. 결국에는 이동 가능한 모든 채널로 이동해보고 해당 채널에서 목표지점까지 +-로만 이동하는 모든 경우의 수를 체크해보아야 하므로  브루트 포스(Brute Force) 방식을 사용해 문제를 풀어야 했다.

 

2. 주의할 점

- 경우의 수를 나누어 생각하면 문제가 훨씬 쉽게 풀린다. 

- 주어지는 목표 채널은 500000까지의 범위이지만, 이동 가능한 채널은 무한대이고, 0 보다 작은 채널은 없다는 점을 다시 한 번 생각해보아야 한다. 만약 목표 채널이 500000이고 모든 버튼이 고장나 +-만으로 이동해야 한다면, 0에서 500000로 이동(+500000)할 수도 있지만, 1000000에서 500000로 이동(-500000)할 수도 있는 것이다.

- 고장난 버튼이 아무것도 없다면, 세번째 줄의 입력은 없어진다. 입력으로 인해 런타임 에러가 나지 않도록 조심하자.

 

3. 소스코드(Java)

// boj 1107 : 리모컨
// 브루트 포스

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

public class boj_01107 {

    private static int N;
    private static int M;
    private static int start = 100;
    private static boolean[] isBroken = new boolean[10];

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = stoi(st.nextToken());
        M = stoi(br.readLine());
        if (M > 0) st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; ++i) isBroken[stoi(st.nextToken())] = true;

        // case 1: +-만으로 start에서 N 도달
        int ans = Math.abs(N - start);
        for (int now = 0; now <= 1000000; ++now) {
            // case 2: 번호를 눌러 now에 도달 후, +-를 사용해 N에 도달
            int tmp = switchChannel(now);
            if (tmp > 0) {
                ans = Math.min(ans, tmp + Math.abs(now - N));
            }
        }
        System.out.print(ans);
    }

    private static int stoi(String s) { return Integer.parseInt(s);};

    private static int switchChannel(int channel) {
        char[] nums = Integer.toString(channel).toCharArray();
        for (char num : nums) if (isBroken[num - '0']) return -1;
        return nums.length;
    }
}

4. 여담

- 쉬워보이는 문제였지만, 역시 골드는 골드(solved.ac 상 gold5에 해당하는 문제였다.)