[백준][Gold5]1107 - 리모컨 -JAVA

[문제]

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

1107번: 리모컨

 

[풀이]

- 알고리즘 분류

• 부르트포스 알고리즘 

정리를 하면 원하는 채널로 이동하는 방법은 2가지가 있다. 

1. +,- 로만 이동하는 방법
2. 가장 근접한 채널까지 이동후, 나머지는 +,-로 이동하는 방법 

처음에 1번 방법은 생각을 못했다.

그런데 만약 이동하려는 채널이 102번일 때 고장난 버튼 없다고 해서 102 세자리 수를 누르는 것보다 +를 2번 누르는 것이 더 클릭하는 버튼 횟수가 작다. 이런 경우도 있으므로 1번 케이스와 2번 케이스를 비교해주어야 한다.

 

1번 방법은 이동하려는 채널에서 100을 뺀 절대값을 구하면 되므로 간단하고 2번 방법은 과감하게 부르트포스 알고리즘을 이용하여 가장 근접한 채널을 찾는 방식을 택했다.

부르트 포스는 사용가능한 버튼으로 중복순열을 이용하여 모든 수를 구하고 그 중 가장 근접한 채널을 구하면 된다. 

 

--

부르트포스 문제치고 개인적으로 굉장히 복잡한 문제라고 생각한다. 

자잘하게 신경쓸 것들이 많은 느낌.. 아니나 다를까 백준 질문게시판에도 반례를 찾는 사람들이 굉장히 많았다. 

그리고 사람들이 농담으로 리모콘 부수고 싶은 문제라고도 한다.

내가 도움을 받은 반례 모음집이다. 

https://www.acmicpc.net/board/view/31853

글 읽기 - ****리모컨 질문게시판에있는 모든 반례 모음****

 

[code]

package com.algorithm.baekjoon.gold5;

import java.io.*;
import java.util.*;

public class Test14 {
    public static final int START_CHANNEL = 100; // 처음 위치한 채널
    public static int N; // 이동하려는 채널
    public static boolean[] isUsefulBtns = new boolean[10]; // 채널 클릭 가능 여부
    public static int tempChannel = 100; // 초기 가장 근접한 채널 초기화

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine()); // 이동하려는 채널
        int M = Integer.parseInt(br.readLine()); // 고장난 버튼 개수

        Arrays.fill(isUsefulBtns, true);
        if (M > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= M; i++) {
                int num = Integer.parseInt(st.nextToken());
                isUsefulBtns[num] = false; // 고장났으므로 false로 변경
            }
        }

        // 만약 이동하려는 채널이 처음채널과 그대로라면 이동할 필요 없으므로 바로 0리턴
        if (N == START_CHANNEL) {
            bw.write(0 + "\n");
        } else {
            // 1.오로지 +, -로만 이동하는 횟수
            int num1 = Math.abs(N - 100);

            // 2.원하는 가장 근접한 채널까지 이동한 후 +,-로 이동하는 횟수
            int end = String.valueOf(N).length();
            int start = end - 1 == 0 ? end : end - 1;
            for (int i = start; i <= end + 1; i++) {
                int[] buckets = new int[i];
                solution(isUsefulBtns, buckets, buckets.length);
            }
            int tempLen = String.valueOf(tempChannel).length();
            int num2 = tempLen + Math.abs(N - tempChannel);

            int answer = Math.min(num1, num2);
            bw.write(answer + "\n");
        }

        br.close();
        bw.flush();
        bw.close();
    }

    public static void solution(boolean[] isUsefulBtns, int[] buckets, int k) {
        if (k == 0) {
            String str = "";
            for (int i = 0; i < buckets.length; i++) {
                str += buckets[i];
            }
            int num = Integer.parseInt(str);
            int num1 = Math.abs(N - tempChannel);
            int num2 = Math.abs(N - num);
            tempChannel = num1 <= num2 ? tempChannel : num;
            return;
        }

        int lastIndex = buckets.length - k - 1;
        for (int i = 0; i < isUsefulBtns.length; i++) {
            if (isUsefulBtns[i] == true) {
                buckets[lastIndex + 1] = i;
                solution(isUsefulBtns, buckets, k - 1);
            }
        }
    }
}