21.04.01 - [BOJ] 1107. 리모컨

[suhyunsim]

문제

• 1107

핵심 아이디어

• 숫자 버튼 -> + or - 버튼
• 이동하려고 하는 채널 N (0 <= N <= 500,000)
• 숫자 버튼을 눌러서 이동하는 채널 C (0 <= C <= 1,000,000)
  • 500,000이 아닌 이유 (155,555 -> 500,000보다 511,111 -> 500,000이 더 좋으니까)
• 초기값을 100에서 숫자 안 누르고 이동하는 횟수로 지정

1. 이동할 채널 C 정하기
2. C에 고장난 버튼 있는지 확인
3. 없으면 |C - N| 계산해서 + or - 몇 번 누르는지

어려운 점, 실수

• 채널 C를 찾는 과정을 이해하는데 오래걸렸다.
  • c가 고장난게 하나라도 있으면 증가시킴
  • 고장난게 하나도 없을 때 그 채널을 누르는 것과 초기값과의 비교
  • 그 중에 가장 작은 값을 찾기

풀이

package main.java.com.poogle.BOJ.Q1107;

import java.util.Scanner;

public class Main {
    static boolean[] broken = new boolean[10];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        //고장난 채널 표시
        while (m-- > 0) {
            int x = sc.nextInt();
            broken[x] = true;
        }
        //정답의 초기값 표시: 숫자 버튼을 안 누름
        int ans = n - 100;
        if (ans < 0) {
            ans = -ans;
        }
        //이동의 초기값
        for (int i = 0; i <= 1000000; i++) {
            int c = i;
            //이동여부 판단
            int len = possible(c);
            /*
            100에서 c로 숫자 이동(len)
            c에서 n으로 +/-로 이동(press)
            둘을 더한 값과 초기값을 비교해서 더 작은 값을 고르도록
            */
            if (len > 0) {
                int press = c - n;
                if (press < 0) {
                    press = -press;
                }
                if (ans > len + press) {
                    ans = len + press;
                }
            }
        }
        System.out.println(ans);
    }

    //채널 c로 이동 가능하면 1, 아니면 0
    private static int possible(int c) {
        if (c == 0) {
            //0이 고장나면 이동할수 없음
            if (broken[0]) {
                return 0;
            } else {
                return 1;
            }
        }
        int len = 0;
        while (c > 0) {
            //고장났으면 true -> 0, 아니면 false
            if (broken[c % 10]) {
                return 0;
            }
            len += 1;
            c /= 10;
        }
        return len;
    }
}