Post

BOJ 22251 빌런 호석

BOJ 22251 빌런 호석

https://www.acmicpc.net/problem/22251

문제

치르보기 빌딩은 $1$층부터 $N$층까지 이용이 가능한 엘리베이터가 있다. 엘리베이터의 층수를 보여주는 디스플레이에는 $K$ 자리의 수가 보인다. 수는 $0$으로 시작할 수도 있다. $0$부터 $9$까지의 각 숫자가 디스플레이에 보이는 방식은 아래와 같다. 각 숫자는 7개의 표시등 중의 일부에 불이 들어오면서 표현된다.

예를 들어 $K=4$인 경우에 $1680$층과 $501$층은 아래와 같이 보인다.

빌런 호석은 치르보기 빌딩의 엘리베이터 디스플레이의 LED 중에서 최소 $1$개, 최대 $P$개를 반전시킬 계획을 세우고 있다. 반전이란 켜진 부분은 끄고, 꺼진 부분은 켜는 것을 의미한다. 예를 들어 숫자 $1$을 $2$로 바꾸려면 총 5개의 LED를 반전시켜야 한다. 또한 반전 이후에 디스플레이에 올바른 수가 보여지면서 $1$ 이상 $N$ 이하가 되도록 바꿔서 사람들을 헷갈리게 할 예정이다. 치르보기를 사랑하는 모임의 회원인 당신은 호석 빌런의 행동을 미리 파악해서 혼쭐을 내주고자 한다. 현재 엘리베이터가 실제로는 $X$층에 멈춰있을 때, 호석이가 반전시킬 LED를 고를 수 있는 경우의 수를 계산해보자.


입력

$N, K, P, X$ 가 공백으로 구분되어 첫째 줄에 주어진다.


출력

호석 빌런이 엘리베이터 LED를 올바르게 반전시킬 수 있는 경우의 수를 계산해보자.


제한

  • $1 ≤ X ≤ N < 10^K$
  • $1 ≤ K ≤ 6 $ 
  • $1 ≤ P ≤ 42 $ 

예제 입력 1

9 1 2 5

예제 출력 1

4

LED를 2개까지 바꿀 수 있을 때, 5층에서 3층, 6층, 8층, 그리고 9층으로 바꿔버릴 수 있다.

예제 입력 2

48 2 5 35

예제 출력 2

30

코드

처음 문제를 봤을 때, 비트마스크 문제라고 생각했었다.

하지만, 각 수마다 다른 수로 변환할 때 필요한 반전 개수와 위치가 정해져있기 때문에 굳이 비트마스크로 불가능한 경우까지 체크할 필요는 없어 보였다.

그래서 직접 각 수에서 다른 수로 변환할 때 필요한 반전 개수를 체크해 배열을 초기화하고 문제를 풀었다.

이후에 찾아보니 비트마스크로 문제를 해결한 사람들도 있었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int answer = 0;
    static int N, K, P;
    static int[] X;

    /**
     * 첫 번째 인덱스의 수에서 두 번째 인덱스의 수로 변경시키는데 필요한 반전 개수
     * ex) cost[0][5]가 3이라는 것은 0에서 5로 변경시키기 위해서 3번의 반전이 필요하다는 의미
     */
    static int[][] costs = {
            {0, 4, 3, 3, 4, 3, 2, 3, 1, 2},
            {4, 0, 5, 3, 2, 5, 6, 1, 5, 4},
            {3, 5, 0, 2, 5, 4, 3, 4, 2, 3},
            {3, 3, 2, 0, 3, 2, 3, 2, 2, 1},
            {4, 2, 5, 3, 0, 3, 4, 3, 3, 2},
            {3, 5, 4, 2, 3, 0, 1, 4, 2, 1},
            {2, 6, 3, 3, 4, 1, 0, 5, 1, 2},
            {3, 1, 4, 2, 3, 4, 5, 0, 4, 3},
            {1, 5, 2, 2, 3, 2, 1, 4, 0, 1},
            {2, 4, 3, 1, 2, 1, 2, 3, 1, 0}
    };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        
        // x를 입력받고, 최대 자릿수인 K에 맞게 x의 나머지 자릿수에 0을 채움
        int x = Integer.parseInt(st.nextToken());
        StringBuilder toX = new StringBuilder(String.valueOf(x));
        while (toX.length() != K) {
            toX.insert(0, '0');
        }
        
        // X의 각 자릿수마다 해당하는 수를 배열에 넣음
        X = new int[K];
        StringBuilder start = new StringBuilder();
        for (int i = 0; i < K; i++) {
            X[i] = toX.charAt(i) - '0';
            start.append('0');
        }
        // 초기 검사 층 수는 0층부터 검사 (나중에 0층은 경우의 수에서 제외)
        dfs(0, 0, start.toString());

        // 0층이 가능하면, 정답 경우의 수에서 1 뺌
        int costToZero = 0;
        while (x > 0) {
            int check = x % 10;
            costToZero += costs[check][0];
            x /= 10;
        }
        if(costToZero <= P) {
            answer--;
        }

        // 맨 처음 X층에서 움직이지 않은 경우는 제외하기 위해 1 뺌
        System.out.println(answer - 1);
    }

    static void dfs(int idx, int cost, String floor) {
        if(idx == K) {
            answer++;
            return;
        }

        // 검사 중인 자릿수에 해당하는 X의 수
        int checkNum = X[idx];
        StringBuilder current = new StringBuilder(floor);

        for (int i = 0; i < 10; i++) {
            int newCost = cost + costs[checkNum][i];
            if(newCost <= P) {
                current.deleteCharAt(idx);
                current.insert(idx, i);
                String newFloor = current.toString();
                if(Integer.parseInt(newFloor) > N) {
                    break;
                }

                dfs(idx + 1, newCost, newFloor);
            }
        }
    }
}
This post is licensed under CC BY 4.0 by the author.