문제 링크

풀이

• 각 숫자(0~9)는 7개의 LED로 구성된 배열로 표현된다.
  예를 들어, 숫자 0은 아래와 같이 7개의 LED 중 6개가 켜진 상태로 나타난다

  {1, 1, 1, 1, 1, 1, 0},  //  0
  {0, 1, 1, 0, 0, 0, 0},  //  1
  .
  .
  .

• 층 수를 디스플레이 형태로 변환
  예를 들어 k = 4, x = 12일 경우, [0, 0, 1, 2]로 표현된다.

• 모든 층을 순회하며 가능한 층을 찾는다.
  1층부터 n층까지 반복하면서 현재 층(x)과 각 층을 디스플레이 배열로 변환해 비교한다.
  두 디스플레이를 비교해 숫자를 바꾸기 위해 필요한 LED 변경 횟수를 계산한다.
  변경 횟수가 p 이하이면 해당 층은 변경 가능한 층으로 간주하고 answer를 증가시킨다.

• 이렇게 하면 현재층도 카운트 되므로 마지막에 정답에서 1을 빼주면 된다.

최대 6자리이므로 해당 경우에 각 자릿수 마다 7번 비교, 최대 999999층까지 있으므로 약 $6*7*10^6$번 연산을 하게 된다.

완전탐색으로도 충분히 풀이할 수 있다.

코드

package BOJ;

import java.io.*;
import java.util.*;

public class sol22251 {
    static int n, k, p, x;
    static int[][] nums = {
            {1, 1, 1, 1, 1, 1, 0},  //  0
            {0, 1, 1, 0, 0, 0, 0},  //  1
            {1, 1, 0, 1, 1, 0, 1},  //  2
            {1, 1, 1, 1, 0, 0, 1},  //  3
            {0, 1, 1, 0, 0, 1, 1},  //  4
            {1, 0, 1, 1, 0, 1, 1},  //  5
            {1, 0, 1, 1, 1, 1, 1},  //  6
            {1, 1, 1, 0, 0, 0, 0},  //  7
            {1, 1, 1, 1, 1, 1, 1},  //  8
            {1, 1, 1, 1, 0, 1, 1}   //  9
    };

    public static void main(String[] args) throws Exception {
        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 = Integer.parseInt(st.nextToken());

        int[] curr = toDisplay(x);
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            int[] target = toDisplay(i);
            int required = 0;
            for (int j = 0; j < k; j++) {
                required += reverseCount(curr[j], target[j]);
            }
            if (required <= p) {
                answer++;
            }
        }
        System.out.println(answer - 1);
    }

    public static int reverseCount(int from, int to) {  //  반전 시키는데 필요한 led 칸 수 세기
        int count = 0;
        for (int i = 0; i < 7; i++) {
            if (nums[from][i] != nums[to][i]) {
                count++;
            }
        }
        return count;
    }

    public static int[] toDisplay(int floor) {  //  층을 디스플레이에 표시
        int[] display = new int[k];
        for (int i = k - 1; i >= 0; i--) { 
            display[i] = floor % 10;
            floor /= 10;
        }
        return display;
    }
}