문제 접근

표현할 수 있는 자릿수는 최대 6개임. 그래서 표현가능한 수도 최대 100만이라고 조건에 나옴. 10^K이므로.

우리는 시작 숫자 X를 알고 있음. 그렇다면 그냥 100만개의 수를 자릿수만큼 다 비교해봐도 최대 600만번 비교임. 1초안에 해결 너무 널널함.

이를 위해, 숫자 a에서 숫자b로 자릿수가 이동하기 위해 바꿔야 하는 횟수인 diff배열을 만들었음.

문제 풀이

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

public class Main {
    static int N;

    static int[][] numbers = {
            {1, 1, 1, 0, 1, 1, 1}, // 0
            {0, 0, 1, 0, 0, 1, 0}, // 1
            {1, 0, 1, 1, 1, 0, 1}, // 2
            {1, 0, 1, 1, 0, 1, 1}, // 3
            {0, 1, 1, 1, 0, 1, 0}, // 4
            {1, 1, 0, 1, 0, 1, 1}, // 5
            {1, 1, 0, 1, 1, 1, 1}, // 6
            {1, 0, 1, 0, 0, 1, 0}, // 7
            {1, 1, 1, 1, 1, 1, 1}, // 8
            {1, 1, 1, 1, 0, 1, 1}, // 9
    };

    static int[][] diff = new int[10][10];

    static int[] xDigits;
    static int[] otherDigits;
    static int K;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        xDigits = new int[K];
        init(xDigits, X);
        otherDigits = new int[K];

        for (int i = 0; i <= 9; i++) {
            for (int j = 0; j <= 9; j++) {
                int count = 0;
                for (int k = 0; k < 7; k++) {
                    if (numbers[i][k] != numbers[j][k]) count++;
                }
                diff[i][j] = count;
            }
        }

        int result = 0;
        for (int i = 1; i <= N; i++) {
            if (i == X) continue;
            // X를 i로 바꾸기.
            init(otherDigits, i);
            int count = 0;
            for (int k = 0; k < K; k++) {
                if (xDigits[k] != otherDigits[k]) {
                    count += diff[xDigits[k]][otherDigits[k]];
                }
            }
            if (count <= P) result++;
        }

        System.out.println(result);
    }

    static void init(int[] d, int n) {
        Arrays.fill(d, 0);
        int curN = n;
        int i = K - 1;
        while (curN > 0) {
            d[i] = curN % 10;
            i--;
            curN /= 10;
        }
    }

}