[백준] 1107

백준 1107번: 리모컨 문제 풀이

이번 포스팅에서는 백준 1107번 문제인 "리모컨" 문제를 해결하는 과정을 정리하겠습니다. 이 문제는 고장난 버튼이 있는 리모컨을 사용해 특정 채널로 이동할 때 최소한의 버튼 클릭 횟수를 계산하는 문제입니다.

문제 분석

문제는 고장난 버튼이 있을 때, 주어진 채널로 이동하기 위해 가장 적은 횟수로 버튼을 눌러야 하는 상황을 제시합니다. 리모컨에는 0부터 9까지의 숫자 버튼과 채널을 올리고 내릴 수 있는 +, - 버튼이 있습니다.

해결 전략

문제를 해결하기 위해 몇 가지 접근 방식을 고려했습니다:

1. +, - 버튼만 사용하는 경우:

   • 현재 채널(기본 채널 100)에서 목표 채널까지 +, - 버튼만을 이용해 이동하는 방법입니다.

2. 숫자 버튼을 사용한 접근:

   • 고장나지 않은 숫자 버튼을 이용해 최대한 목표 채널에 가까운 채널을 입력하고, 남은 차이를 +, - 버튼으로 이동하는 방법입니다.

3. 상향 및 하향 접근:

   • 목표 채널에서 위쪽과 아래쪽으로 가능한 채널을 탐색하며, 고장난 버튼을 피해서 가장 가까운 채널을 찾습니다.

코드 구현

문제를 해결하기 위한 코드는 아래와 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class P1107 {
    private static boolean checkNumber(int number, int[] brokenNumber) {
        String numStr = Integer.toString(number);

        for (int i = 0; i < numStr.length(); i++) {
            for (int j = 0; j < brokenNumber.length; j++) {
                if (Character.getNumericValue(numStr.charAt(i)) == brokenNumber[j]) {
                    return false;
                }
            }
        }
        return true;
    }

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

        String num = br.readLine();
        int numLength = num.length();
        int[] number = new int[numLength];

        for (int i = 0; i < numLength; i++) {
            number[i] = Character.getNumericValue(num.charAt(i));
        }

        int n = Integer.parseInt(br.readLine());
        int[] brokeNumber = new int[n];
        int sum = 0;
        if (n != 0) {
            String[] line = br.readLine().split(" "); 
            for (int i = 0; i < n; i++) {
                brokeNumber[i] = Integer.parseInt(line[i]);
                sum += brokeNumber[i];
            }
        }

        int count = Math.abs(Integer.parseInt(num) - 100); 

        int countUpper = n == 10 ? 500000 : 0;
        int numUp = Integer.parseInt(num);
        boolean pressOther = true;

        if (n == 9 && sum == 45) {
            pressOther = false;
            countUpper = 500000;
        }

        if (n != 10 && pressOther) {
            while (numUp >= 0) {
                if (checkNumber(numUp, brokeNumber)) {
                    countUpper += Integer.toString(numUp).length();
                    break;
                }
                countUpper++;
                numUp++;
            }
        }

        int countDown1 = n == 10 ? 500000 : 0;
        int countDown2 = 0;
        int numDown = Integer.parseInt(num);

        if (n != 10) {
            if (numDown == 0) {
                countDown1 = 500000;
            }

            while (numDown >= 0) {
                if (checkNumber(numDown, brokeNumber)) {
                    countDown1 = Integer.toString(numDown).length();
                    break;
                } else {
                    countDown1 = 500000;
                }
                countDown2++;
                numDown--;
            }
        }
        countDown2 += countDown1;

        count = Math.min(count, countUpper);
        count = Math.min(count, countDown2);

        System.out.println(count);
    }
}

코드 설명

1. 고장난 버튼 체크:

   • checkNumber 함수는 주어진 숫자에서 고장난 버튼이 포함되어 있는지 확인합니다. 포함되어 있으면 false, 아니면 true를 반환합니다.

2. +, - 버튼만 사용하는 경우:

   • 현재 채널 100에서 목표 채널까지의 거리(버튼 클릭 횟수)를 계산합니다. 이 값은 Math.abs(Integer.parseInt(num) - 100)로 구할 수 있습니다.

3. 숫자 버튼을 이용한 상향 탐색:

   • 목표 채널보다 큰 채널 중 고장난 버튼이 없는 첫 번째 채널을 찾아 이동 횟수를 계산합니다. 만약 고장난 버튼이 전부이면 무한대(500000)로 설정합니다.

4. 숫자 버튼을 이용한 하향 탐색:

   • 목표 채널보다 작은 채널 중 고장난 버튼이 없는 첫 번째 채널을 찾아 이동 횟수를 계산합니다. 마찬가지로 고장난 버튼이 전부이면 무한대로 설정합니다.

5. 최소 이동 횟수 계산:

   • 각 접근 방법에서 얻은 이동 횟수 중 가장 작은 값을 선택하여 출력합니다.

사고 흐름 정리

1. 문제 분석: 고장난 버튼이 있는 경우 어떻게 목표 채널로 이동할 수 있을지 고민합니다. 가능한 모든 이동 방법을 탐색해 최소 이동 횟수를 찾아야 합니다.

2. 조건 처리: 고장난 버튼이 전부일 경우나, 숫자 버튼을 사용할 수 없을 경우에 대한 예외 처리를 고려합니다.

3. 탐색: 목표 채널을 중심으로 상향 및 하향 탐색을 통해 가능한 채널을 찾습니다. 이때, 고장난 버튼이 없을 때만 해당 채널로 이동합니다.

4. 최적화: +, - 버튼만을 사용한 경우와 숫자 버튼을 사용한 경우 중 최소 이동 횟수를 선택합니다.

마무리

이 문제는 주어진 조건을 바탕으로 모든 가능성을 탐색해야 하는 전형적인 완전 탐색 문제입니다. 고장난 버튼을 고려해 예외 상황을 처리하고, 다양한 접근 방식을 통해 최적의 해결책을 찾는 과정이 중요합니다. 코드를 통해 문제 해결 방법을 이해하는 데 도움이 되었기를 바랍니다. 다음에도 더 흥미로운 문제로 찾아오겠습니다!