자바(백준) 1107 리모컨

오답 노트 & 새로 알게 된 점

문제를 읽자마자 백트래킹으로 접근했다.

맞왜틀을 시전 후, 게시판에 반례를 보는 중에

99999

2

9 8

경우에 100000 - 1 로 2가 나오는데 나의 답은 27777이 나왔다.

백트래킹을 하여 자릿수마다 비교하기 때문에 100,000은 나올 수 없었다.

그래서 어떻게 풀어야하는지 고민을 했지만, 생각이 나질 않아 구글링을 했다.

 

참고 블로그 : https://moonsbeen.tistory.com/64

 

우리가 비교해야할 값은 
+ 또는 -만 누를 경우 vs 숫자를 누르고 N과 차이 만큼 +나 -를 누를 경우이다.

그래서 초기값을 Math.abs(N-100)으로 한다. 이 경우가 + 또는 - 만 누를 경우이다.

 

이제 리모컨을 눌러 나올 수 있는 최대값을 생각해서 0부터 완전 탐색하며 가장 가까운 수를 구해야한다.

최대값을 999999로 설정할 수 있는 이유는

문제에서 N이 최대 500,000이라 했다. 이 때, 9를 제외한 나머지 버튼들이 모두 고장났을 때, 500000 중에

가장 가까운 수는 999999이기 때문이다. 문제에서 채널은 무한대만큼 있다고 하여 이 부분을 간과한 것 같다.

 

위와 같은 이유로 0 ~ 999999까지 탐색하면 된다.

• 각 숫자의 버튼을 비교
  • 고장O
    • 반복문을 빠져나가고 다음 for문 진행
  • 고장X
    • 자릿수(버튼을 자릿 수만큼 눌러야하기 때문) + N과의 차이값(차이만큼 +나 -를 눌러야함
• click(초기값)과 위에서 구한 value값 중 최솟값을 구하기

 

---

코드

 

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N;
    static boolean error[];
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        int click = Math.abs(N - 100); //+, -를 누르는 횟수
 
        for (int i = 0; i < 1000000; i++) {
            String s = String.valueOf(i);
            int len = s.length();
 
            boolean isBreak = false;
            for (int j = 0; j < len; j++) {
                if (error[s.charAt(j) - '0']) {
                    isBreak = true;
                    break;
                }
            }
 
            //i에서 누른 버튼들이 모두 고장나지 않을 경우
           if (!isBreak) {
                int value = Math.abs(N - i) + len;
                click = Math.min(value, click);
            }
        }
        System.out.println(click);
    }
 
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String sN = br.readLine();
 
        N = atoi(sN);
 
        int errorCnt = atoi(br.readLine());
        error = new boolean[10];
 
        //고장난 게 없을 경우 예외처리
       if(errorCnt == 0) return;
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        for (int i = 0; i < errorCnt; i++) {
            int idx = atoi(st.nextToken());
            error[idx] = true;
        }
    }
}