백준 1107번 리모컨 [브루트 포스] :: 마이구미

이번 글은 백준 알고리즘 문제 1107번 "리모컨" 을 다뤄본다.

문제 접근 방법은 브루트 포스. 즉, 노가다로 해결할 수 있다.

1107번 리모컨 - https://www.acmicpc.net/problem/1107

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 망가져있는지 주어졌을 때, N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 

수빈이가 지금 보고 있는 채널은 100번이다.

본인은 처음에 단순히 채널을 한자리씩 분해하여 목표 채널에 가깝게 가는 방식으로 접근했다.

하지만 이 경우 반례가 너무 많이 존재한다. (문제를 풀어봤다면 이해하리라 생각한다)

그래서 생각한 방법이 브루트 포스이다.

사실상 테스트 케이스도 500,000 이기 때문에 충분히 가능하다.

문제에서 목표 채널로 이동하기 위한 방법은 3가지로 분류할 수 있다.

1. 숫자 버튼을 통해 목표 채널에 도달한다.
2. 숫자 버튼을 통해 가까운 채널로 이동한 후, + 또는 - 버튼을 통해 목표 채널에 도달한다.
3. + 또는 - 버튼을 통해 목표 채널에 도달한다.

본인이 구현한 방법은 단순히 0~88888 각 채널이 목표 채널로 이동할 수 있는 횟수를 구하면서 최소를 뽑아낸다.

테스트 케이스는 500000이지만, 채널을 500000 이상으로 이동한 다음 - 버튼을 이용할 수 있는 경우도 있다.

대표적인 입력 예는 아래와 같다.

500000
8
0 1 2 3 4 5 6 7

본인의 구현 방큰 틀은 아래와 같다.

1. 언급한 이동할 수 있는 방법 3번을 기준.

int ans = Math.abs(n - 100); // + 또는 - 버튼으로만 이동 횟수를 기준.

2. 숫자 버튼을 통해 이동할 수 있는 채널인지 확인.

for (int i = 0; i <= 888888; i++) {
    // i는 번호 버튼을 눌러 가까운 번호로 이동으로 가정.
    boolean flag = false;
    String current = String.valueOf(i);
    int len = current.length();

    for (int j = 0; j < len; j++) {
        int value = current.charAt(j) - '0';

        if (!check(remocon, value)) {
            flag = true;
            break;
        }

    }
    // 아래 3번
    ............
}

3. 숫자 버튼을 통해 이동할 수 있을 경우 

if (!flag) {
    // 숫자 버튼 횟수 + 이동한 번호와 목표 번호간의 차이
    if (ans > Math.abs(i - n) + len) {
        ans = Math.abs(i - n) + len;
    }

}

전체 소스를 보면 더욱 이해가 빠를 거라 생각한다.

소스는 아래 Github URL을 참고하길 바란다.

백준 알고리즘 1107번 리모컨 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/algorithm/Brute-Force/1107.java