[BruteForce] 백준 1107: 리모컨

1107번: 리모컨 (acmicpc.net)

1107번: 리모컨

이동해야 할 채널이 주어지고, 고장난 숫자 버튼이 주어진다.

 

그럼 수빈이가 목표 채널로 이동하는 경우는 다음 두 가지이다.

 

1. 정직하게 +/- 버튼만 눌러서 목표 채널까지 이동한다.

2. 현재 가능한 숫자 버튼들의 조합으로 가장 가까운 지점까지 이동한 후, 거기서 +/-버튼을 눌러서 추가로 이동한다.

 

1. 번의 경우는 단지 현재 채널(100번)과 목표 채널 사이의 절대값이 될 것이다. 

byPlusMinus = Math.abs(N-100);

 

2. 번의 경우, 중복순열을 이용해야 한다.(숫자들의 순서가 의미 있음 + 한 번 선택한 숫자를 다시 선택할 수 있음)

 

나는 재귀함수를 이용해 구현하였는데, 먼저 기존에 구현하던 것과 다르게 무조건 r자리의 중복순열을 찾는 것이 아니라 최대 r자리까지의 중복순열을 찾는 문제인 점을 고려해야 했다. 가령 9999로 가는데, 9998+1로 이동할 수도 있을 것이고 10002-3으로 이동할 수도 있을 것이다. 요컨대 "r자릿수의 중복순열을 찾을 거야!" 가 아니라, "주어진 버튼들로 가능한 중복수열의 경우의 수를 찾을 건데, 자릿수가 아니라 목표채널 N과의 거리가 얼마나 되는지 다 검사해서 가장 가까운 녀석을 찾을 거야!"로 접근해야 한다. 

 

따라서 r자릿수를 모두 채웠을 때(depth==r) 검사하고 update&return 하는 식으로 구현했던 이전 방식들과 다르게 매 재귀함수 호출 시마다 (기존 가장 가까운 채널과 목표채널 간의 절대값)vs(현 채널(currentNum)과 목표채널 간의 절대값)을 비교했다.

 

static void findNearest(int[] buttons, int depth, int r, int currentNum)
    {
        if(Math.abs(nearest-N)>Math.abs(N-currentNum)){
            if(currentNum<10){
                if(buttons[currentNum]!=-1){
                    nearest = currentNum;
                }
            }else{
                nearest = currentNum;
            }
        }else if(Math.abs(nearest-N)==Math.abs(N-currentNum)){
            //더 버튼 누르는 수가 가까운 쪽으로 감.
            int nearest_copy = nearest;
            int currentNum_copy = currentNum;
            int nearest_buttons = nearest;
            int currentNum_buttons = currentNum;

            while(nearest_copy!=0){
                nearest_copy/=10;
                nearest_buttons++;
            }

            while(currentNum_copy!=0){
                currentNum_copy/=10;
                currentNum_buttons++;
            }

            nearest = (nearest_buttons>currentNum_buttons)?currentNum:nearest;
        }
        if(depth==r){
            return;
        }

        for(int i=0;i<buttons.length;i++){
            if(buttons[i]!=-1){
                findNearest(buttons,depth+1,r,currentNum*10+buttons[i]);
            }
        }

잠시 멈춰서 이 부분을 자세히 보자. 

else if(Math.abs(nearest-N)==Math.abs(N-currentNum)){
            //더 버튼 누르는 수가 가까운 쪽으로 감.
            int nearest_copy = nearest;
            int currentNum_copy = currentNum;
            int nearest_buttons = nearest;
            int currentNum_buttons = currentNum;

            while(nearest_copy!=0){
                nearest_copy/=10;
                nearest_buttons++;
            }

            while(currentNum_copy!=0){
                currentNum_copy/=10;
                currentNum_buttons++;
            }

            nearest = (nearest_buttons>currentNum_buttons)?currentNum:nearest;
        }

이 부분을 고려하지 않아서 이틀이나 붙잡고 있었다. 이 부분을 제외하고 nearest-N vs currentNum-N간 절대값만 비교하고 새로 찾은 채널에서의 절대값이 더 작은 경우만 nearest를 업데이트했는데, 잠깐 아래 경우를 생각해 보자.

 

가령 내가 가려는 채널이 8이고, 현재 사용 불가한 숫자 버튼은 0,2,3,4,6,7,8,9라고 하자.

 

그럼 5->8로 갈 수도 있고, 11->8로 갈 수도 있어진다. 이 경우 당연히 5에서 +버튼을 3번 눌러 8로 가는 길이 버튼을 하나 더 적게 누르겠지만, 문제는 5와 11이 8과 모두 똑같이 3씩 떨어져 있기 때문에 nearest를 업데이트할 때 제대로 반영이 안 된다는 점이다.

 

즉, 목표 채널과의 절대값이 같은 두 수의 경우 어느 수가 더 버튼을 적게 눌러서 갈 수 있는지 구별하는 코드를 꼭 넣어야 한다.

 

그 외에는 구현에 별 어려움은 없었다. 포스팅 상단에 써 놓은 논리('가장 가까운 수 찾아서 +- 로 이동 vs 순수 +-만 가지고 이동)를 열심히 써 보면 된다.

 

코드 첨부하고 마친다.

 

import java.io.*;

public class Main {
    static int N;
    static int M;
    static int[] buttons = {0,1,2,3,4,5,6,7,8,9};
    static int byPlusMinus;
    static int byButtons;
    static int nearest=100;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        if(N<0&&N>500000){
            System.exit(0);
        }
        M = Integer.parseInt(br.readLine());

        if(M!=0){
            String[] disabledButtons = br.readLine().split(" ");
            for(int i=0;i< disabledButtons.length;i++){
                buttons[Integer.parseInt(disabledButtons[i])]=-1;
            }
        }

        findNearest(buttons,0,6,0);

        //nearest 번호로 가기 위해 눌러야 하는 버튼 개수 파악
        int nearest_copy = nearest;
        //nearest가 한 자리 수일 때는 nearest_copy/10==0이어서 카운팅 안되는 문제 발생.
        if(nearest_copy/10==0){
            byButtons=1;
        }else{
            while(nearest_copy!=0){
                nearest_copy/=10;
                byButtons++;
            }
        }

        //nearest에서 N으로 가기 위해 눌러야 하는 +- 버튼 개수 파악
        byButtons+=Math.abs(N-nearest);
        //+-버튼만을 사용해 100에서 N으로 가기 위한 버튼 개수 파악
        byPlusMinus = Math.abs(N-100);

        System.out.println(Math.min(byButtons,byPlusMinus));
    }

    //현재 사용 가능한 버튼들의 중복 순열 중 가장 N과 가까운 번호를 찾는다.
    static void findNearest(int[] buttons, int depth, int r, int currentNum)
    {
        if(Math.abs(nearest-N)>Math.abs(N-currentNum)){
            if(currentNum<10){
                if(buttons[currentNum]!=-1){
                    nearest = currentNum;
                }
            }else{
                nearest = currentNum;
            }
        }else if(Math.abs(nearest-N)==Math.abs(N-currentNum)){
            //더 버튼 누르는 수가 가까운 쪽으로 감.
            int nearest_copy = nearest;
            int currentNum_copy = currentNum;
            int nearest_buttons = nearest;
            int currentNum_buttons = currentNum;

            while(nearest_copy!=0){
                nearest_copy/=10;
                nearest_buttons++;
            }

            while(currentNum_copy!=0){
                currentNum_copy/=10;
                currentNum_buttons++;
            }

            nearest = (nearest_buttons>currentNum_buttons)?currentNum:nearest;
        }
        if(depth==r){
            return;
        }

        for(int i=0;i<buttons.length;i++){
            if(buttons[i]!=-1){
                findNearest(buttons,depth+1,r,currentNum*10+buttons[i]);
            }
        }
    }
}