[백준]22251: 🤷‍♂️빌런 호석 - JAVA

[백준]22251: 빌런 호석

22251번: 빌런 호석

풀이

🪑 굉장히 재미있는 구현 문제였다.

 

📝 문제의 조건을 정리해 보자.

• 7개의 표시등으로 이루어진 디스플레이를 K개의 자리수로 표현한다.
• 디스플레이 표시등 중에 최소 1개, 최대 P개를 반전시킨다. (자기자신으로 반전하는 경우는 제외한다.)
• 반전 이후에도 올바른 수가 보여져야 하며 수는 1이상 N이하여야 한다.
• 반전시킬 표시등을 고를 수 있는 경우의 수를 계산한다.

 

 

🙋‍♀️ 문제 풀이 과정을 도출해 내는 과정을 다음과 같았다.

- 처음에는 '백트랙킹'으로 반전시킬 표시등의 수를 골라 반전시켜서 수를 만들 수 있는지, 그리고 반전시킨 수가 범위내인지 확인하여 푸는 방법이 떠올랐다.

- 먼저 반전시켜서 숫자가 되는지 확인하는 방법으로 미리 숫자에 해당하는 디스플레이 정보를 만들어 놓는것이 좋겠다고 생각했다.

- 백트랙킹으로 풀면 표시등의 수를 골라 반전시킬 수 있는 수를 찾는 과정이 복잡하고 지저분해졌다. 이 방법이 아니라는 생각이 들 정도로..(4자리 숫자에서 5개를 반전시킨다고 했을때, 첫 숫자에서 1~5개,, 나머지 자리수에서 1~5개,, 이런식으로 너무 많은 탐색 과정이 필요하다.)

- 그래서 완전탐색으로 풀되, 확인하는 숫자를 표시등의 수가 아닌 반전시켜서 만들 수 있는 수로 하였다.

 

 

🔧 풀이 과정을 알아보자!

1. 표시등에 대한 정보를 미리 입력해 둔다.
2. 현재 층을 디스플레이 정보로 변환해 준다.
3.  1 ~ N 중에 P개 이내의 표시등을 반전시켜 해당 수를 만들 수 있는지 확인한다.

 

🔹 표시등에 대한 정보를 미리 입력해 둔다.

- 숫자 하나를 표시하는데 필요한 표시등 수는 7개이다. 

- 표시등에 하나씩 인덱스를 부여하여 해당 표시등으로 만들 수 있는 숫자의 모양을 입력해 둔다.

 

🔹 현재 층을 디스플레이 정보로 변환해 준다.

- 예를 들어 현재 층이 501층이라고 할 때, K가 4라면 0501로 표시해 주어야 한다.

- 또한 몇 개의 표시등이 반전되었는지 한 자리수씩 확인을 해 주어야 하기 때문에 숫자를 하나씩 끊어서 배열에 담아 주었다.

 

🔹 1 ~ N 중에 P개 이내의 표시등을 반전시켜 해당 수를 만들 수 있는지 확인한다.

- 1 ~ N층을 완전 탐색한다.

- 이때 P개 이내의 표시등을 반전시켜 해당 숫자를 만들 수 있다면 만들 수 있는 수가 된다.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n, k, p, x;
    static int[][] display = {{1, 1, 1, 0, 1, 1, 1}, //0
                            {0, 0, 1, 0, 0, 0, 1}, //1
                            {0, 1, 1, 1, 1, 1, 0}, //2
                            {0, 1, 1, 1, 0, 1, 1}, //3
                            {1, 0, 1, 1, 0, 0, 1}, //4
                            {1, 1, 0, 1, 0, 1, 1}, //5
                            {1, 1, 0, 1, 1, 1, 1}, //6
                            {0, 1, 1, 0, 0, 0, 1}, //7
                            {1, 1, 1, 1, 1, 1, 1}, //8
                            {1, 1, 1, 1, 0, 1, 1}}; //9
    static long count = 0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        //입력
        String s = bf.readLine();
        StringTokenizer st = new StringTokenizer(s);
        
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        p = Integer.parseInt(st.nextToken());
        x = Integer.parseInt(st.nextToken());
        //입력 끝
 
        int[] x_digit = num_to_digit(x);
        check(0, x_digit);
        System.out.println(count);
    }
 
    public static void check(int num, int[] x_digit) {
        for(int i = 1; i <= n; i++) {
            if(i == x) continue;
            if(can_reverse(i, x_digit)) count++;
        }
    }
 
    public static boolean can_reverse(int target, int[] x_digit) {
        int[] target_digit = num_to_digit(target);
 
        int diff_count = 0;
        for(int i = 0; i < k; i++) {
            for(int j = 0; j < 7; j++) {
                if(display[x_digit[i]][j] != display[target_digit[i]][j]) {
                    diff_count++;
                    if(diff_count > p) return false;
                }
            }
        }
        return true;
    }
 
    public static int[] num_to_digit(int x) {
        int[] result = new int[k];
        for(int i = k - 1; i >= 0; i--) {
            result[i] = x % 10;
            x /= 10;
        }
        return result;
    }
}