[ 백준 ] 1107 리모컨

codesver·2022년 12월 14일
0

Baekjoon

목록 보기
3/72
post-thumbnail

Analyze

이 문제에서는 주의해야 하는 점이 몇 개가 있다.

  1. 입력의 차이

    일반적인 입력의 경우에는 목표 숫자, 고장 버튼 개수, 고장 버튼 숫자들로 주어진다.

    하지만 고장 버튼 개수가 0개인 경우가 존재한다.

    이 때는 고장 버튼 숫자들이 주어지지 않는다.

    그렇기 때문에 2가지의 경우를 나누어 생각하지 않고 고장 버튼 숫자들의 입력을 받는다면

    solution은 고장 버튼 숫자들의 입력을 무한히 기다린다.

    물론 고장 버튼 숫자들을 한 번에 읽지 않고 개수만큼 하나씩 읽으면 무한 대기하지 않는다.

    하지만 고장난 버튼이 없을 경우에는 추가 로직 없이 +-으로만 이동하는 경우와 목표 채널의

    길이 비교만을 통해 answer를 계산할 수 있기 때문에 나누는 것이 좋다.

  2. 검사 숫자

    핵심 알고리즘은 완전 탐색을 통해 특정 채널을 누르고 증감버튼을 통해 목표 채널로 가는

    것이다. 이 때 완전 탐색의 범위를 정해야 하는데 우선 0부터 탐색할 수 있다.

    채널이 무한하기 때문에 상한값이 없다고 생각할 수 있으나 목표 채널의 범위가 정해져

    있기 때문에 탐색의 상한값도 정해져 있다. 목표 채널은 최대 500,000이다.

    만약 1,000,000 이상이 되면 그 밑의 어떤 숫자를 통해 목표 채널로 가는 것보다

    오래 걸린다. 그렇기 때문에 최대 999,999를 상한값으로 정해야 한다.

Solution

핵심 알고리즘은 다음과 같다.

  1. 각각의 입력 숫자들을 완전 탐색한다.

  2. 숫자를 번호판으로 누를 수 있는지 확인한다.

  3. 누를 수 있으면 누른 후 증감 버튼을 이용해 이동하는 거리를 구한다.

  4. 현재 구해진 최소 거리와 비교한다.

private static final boolean[] isBroken = new boolean[10];

private static void solution() throws IOException {
    int goalNumber = Integer.parseInt(reader.readLine());

    if (Integer.parseInt(reader.readLine()) == 0) {
        result.append(Math.min(
                Math.abs(100 - goalNumber),
                String.valueOf(goalNumber).length()));
    } else {
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        while (tokenizer.hasMoreTokens())
            isBroken[Integer.parseInt(tokenizer.nextToken())] = true;

        int count = Math.abs(100 - goalNumber);
        for (int i = 0; i <= 999999; i++)
            if (canClickButton(i))
                count = Math.min(
                        count, 
                        String.valueOf(i).length() + Math.abs(i - goalNumber));
        result.append(count);
    }
}

private static boolean canClickButton(int number) {
    char[] digits = String.valueOf(number).toCharArray();
    for (char digit : digits)
        if (isBroken[Character.getNumericValue(digit)])
            return false;
    return true;
}
profile
Hello, Devs!

0개의 댓글