백준 22251 빌런 호석 (Java)

1. 문제

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

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

입력

 

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

출력

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

 

2. 풀이

x를 n의 범위 내에서 p의 반전 횟수를 가지고 바꾸는 경우의 수를 구하는 문제이다. 각 숫자에 대해 서로 바꿀 때의 반전 횟수는 LED를 비교하여 서로 다른 것의 개수와 같다. 이를 알기 위해 각 숫자에 대한 LED의 켜짐/꺼짐 여부를 저장해야 한다.

    static int[][] digit = {{1, 1, 1, 0, 1, 1, 1},
            {0, 0, 1, 0, 0, 1, 0},
            {1, 0, 1, 1, 1, 0, 1},
            {1, 0, 1, 1, 0, 1, 1},
            {0, 1, 1, 1, 0, 1, 0},
            {1, 1, 0, 1, 0, 1, 1},
            {1, 1, 0, 1, 1, 1, 1},
            {1, 0, 1, 0, 0, 1, 0},
            {1, 1, 1, 1, 1, 1, 1},
            {1, 1, 1, 1, 0, 1, 1}};

        for(int i = 1; i <= n; i++) {
            if(i == x) continue;
            if(checkP(i, x)) ans++;
        }

1층부터 n층까지의 각 경우를 모두 탐색하면서 x에서 i로 바꿀 수 있다면 해당 수를 경우의 수로 추가해주면 된다.

    static boolean checkP(int a, int b) {
        int cnt = 0;

        String aStr = ((Integer) a).toString();
        String bStr = ((Integer) b).toString();

        while (aStr.length() < k) {
            aStr = '0' + aStr;
        }
        while (bStr.length() < k) {
            bStr = '0' + bStr;
        }

        for(int i = 0; i < k; i++) {
            for(int j = 0; j < 7; j++) {
                if(digit[aStr.charAt(i)-'0'][j] != digit[bStr.charAt(i)-'0'][j]) {
                    cnt++;
                    if(cnt > p) return false;
                }
            }
        }

        return true;
    }

이를 판단하는 로직이다. 우선 각 수의 자릿수를 비교하기 위해 문자열로 바꾸고, k 자리수로 맞춰야 하므로 모자라다면 0을 앞에 붙여준다. 이후 각 자리 수에 대해 x에서 i로 바꾸기 위한 반전 횟수를 구해준다. 같은 위치의 LED가 서로 다르다면 해당 부분은 반전이 필요하므로 cnt를 올려주는 것이다. 총 p개 까지 반전이 가능하므로 이를 넘어서면 false, 그렇지 않고 반복문을 무사히 빠져나오면 true를 반환해준다.

3. 코드 전문

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int n, k, p, x;
    static int[][] digit = {{1, 1, 1, 0, 1, 1, 1},
            {0, 0, 1, 0, 0, 1, 0},
            {1, 0, 1, 1, 1, 0, 1},
            {1, 0, 1, 1, 0, 1, 1},
            {0, 1, 1, 1, 0, 1, 0},
            {1, 1, 0, 1, 0, 1, 1},
            {1, 1, 0, 1, 1, 1, 1},
            {1, 0, 1, 0, 0, 1, 0},
            {1, 1, 1, 1, 1, 1, 1},
            {1, 1, 1, 1, 0, 1, 1}};

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        int ans = 0;

        n = Integer.parseInt(tokenizer.nextToken());
        k = Integer.parseInt(tokenizer.nextToken());
        p = Integer.parseInt(tokenizer.nextToken());
        x = Integer.parseInt(tokenizer.nextToken());

        for(int i = 1; i <= n; i++) {
            if(i == x) continue;
            if(checkP(i, x)) ans++;
        }

        System.out.println(ans);

    }

    static boolean checkP(int a, int b) {
        int cnt = 0;

        String aStr = ((Integer) a).toString();
        String bStr = ((Integer) b).toString();

        while (aStr.length() < k) {
            aStr = '0' + aStr;
        }
        while (bStr.length() < k) {
            bStr = '0' + bStr;
        }

        for(int i = 0; i < k; i++) {
            for(int j = 0; j < 7; j++) {
                if(digit[aStr.charAt(i)-'0'][j] != digit[bStr.charAt(i)-'0'][j]) {
                    cnt++;
                    if(cnt > p) return false;
                }
            }
        }

        return true;
    }
}