[JAVA75] 1107. 리모컨

1107. 리모컨 (G5)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	119613	29938	21117	23.435 %

문제

 

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

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

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

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

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

---

summary

리모컨 사용 최소 횟수 구하기

• 시작 채널은 100임
• 고장난 버튼은 0~9 중에서 주어짐

strategy

브루트포스 (완전탐색)

• 시작 번호부터 목적지 번호를 기본 이동 횟수로 체크 (목적지번호 - 100)
• 각 자리수 숫자 체크할 때 0은 로직에서 벗어나기 때문에 0은 예외로 체크 
• 각 자리수를 10으로 나눈 몫과 나머지로 유효한 숫자인지 체크 (checkDiff)  
• 해당 숫자가 목적지 번호까지 얼마나 차이나는지 체크 (checkDiff)
• 한 번이라도 이동 가능한 숫자를 발견하면 비교 후 종료 (break)

note

• 0 ≤ N ≤ 500,000
• 0 ≤ M ≤ 10

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

public class Main {
    static int startNum = 100, endNum, N, minDiff, cnt;
    static boolean[] arr = new boolean[10];
    static boolean flag;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        endNum = Integer.parseInt(br.readLine());
        N = Integer.parseInt(br.readLine());

        if(N > 0) {
            StringTokenizer input = new StringTokenizer(br.readLine());
            for(int n = 0; n < N; n++) {
                arr[Integer.parseInt(input.nextToken())] = true;
            }
        }

        minDiff = Math.abs(endNum - startNum);

        if(minDiff != 0) {
            if(!arr[0]) minDiff = Math.min(minDiff, endNum + 1); // 0 누르고 목적지 번호로 이동
            
            for(int n = endNum; n > 0; n--) { // endNum 부터 1 까지

                cnt = checkNum(n);
                
                if(flag) continue; // 접근 불가능 숫자
                
                minDiff = Math.min(cnt, minDiff); 
                break; // 더 나은 결과가 나오지 않기 때문에 종료
            }

            for(int n = endNum + 1; n < 1_000_000; n++) { // endNum + 1 부터 1_000_000 까지
                
                cnt = checkNum(n);

                if(flag) continue; // 접근 불가능 숫자
                
                minDiff = Math.min(cnt, minDiff);
                break; // 더 나은 결과가 나오지 않기 때문에 종료
            }
        }
        
        System.out.println(minDiff);
        br.close();
    } 

    private static int checkNum(int num) {
        int cnt += Math.abs(endNum - nim);
        
        flag = false;
        while(num > 0) {
            cnt++;
            if(arr[num % 10]) flag = true;
            num /= 10;
        }

        return cnt;
    }
}

문제	결과	메모리	시간	언어코드	길이
1107	맞았습니다!!	14416 KB	140 ms	Java 11 / 수정	2017 B

memo

• 숫자 범위 보면 브루트포스가 가능할 것 같은데, 골드 문제여서 살짝 고민했다. (하지만 얕잡아본거였다. 쉽지 않았다.)
• 반례 없었으면 해결 못했다

0
0
// 정답 : 1

0
2
0 1
// 정답 : 3