[BOJ] 1107. 리모컨 - BF

[BOJ] 1107. 리모컨 - BF

Problem

제출일 : 2020-02-13

문제 풀이 시간 : 2H

난이도 : ★★★☆

---

link : https://www.acmicpc.net/problem/1107

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

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

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

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

input

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

Output

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

Example

input

500000
8
0 2 3 4 6 7 8 9

output

11117

Solution & Inpression

3번을 다시 풀어 통과한 문제

처음 문제를 접근할때 goal에 가장 근접한 값을 찾아 계산하려 했지만 생각보다 예외가 많아 완전 탐색을 수행했다.

입력으로 주어지는 최대 값은 500,000 으로 6자리의 숫자이기때문에 0~999999을 탐색을 수행했다.

2시간이 넘게 붙잡고 문제를 풀었지만 쉽게 푸려니 한없이 쉽게 풀어지는 문제라고 생각이 든다.

Code1

언어 : JAVA

메모리 : 109,160 kb

실행시간 : 384 ms

import java.io.FileInputStream;
import java.util.Scanner;

public class Main {
    static boolean[] broken;

    public static void main(String[] args) throws Exception {
        // System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        int start = 100;
        int goal = sc.nextInt();
        if (start == goal) {
            System.out.println(0);
            return;
        }
        int N = sc.nextInt();
        broken = new boolean[10];
        for (int i = 0; i < N; i++) {
            broken[sc.nextInt()] = true;
        }
        int ans = Math.abs(goal - start);
        for (int i = 0; i <= 1000000; i++) { // 숫자 버튼으로 이동하는 채널
            if (go(i)) {
                int tmp = Math.abs(i - goal) + ("" + i).length(); // +나 -를 몇 번 눌러야 하는지 계산
                if (ans > tmp) {
                    ans = tmp;
                }
            }
        }
        System.out.println(ans);
    }

    private static boolean go(int x) {
        String str = "" + x;
        for (int i = 0; i < str.length(); i++) {
            if (broken[str.charAt(i) - '0'])
                return false;
        }
        return true;
    }
}