아이디어

• 숫자의 7-segment 표현을 비트열로 옮길 것이다.
  
  • 각 (빨간 숫자)번 비트가 켜져 있으면 그 막대기가 켜져 있다고 한다.
• 그 결과 길이가 최대 7인 비트열을 얻는다.
• 이를 이용해 6자리 이하 임의의 십진수를 비트열로 나타낼 것이다.
  • 수의 각 자릿수에 대해 7-seg 비트열을 구하고, 이를 비트합으로 7자리씩 연달아 합쳐 수를 표현한다.
  • 예를 들어, $X = 248$이라면 숫자 ‘2,’ ‘4’, ‘8’은 각각 1011011, 1100110, 1111111이므로 248에 대한 비트열 표현은 101101111001101111111이 된다.
  • 1 이상 $N$ 미만 수는 1~6자리이므로 비트열의 길이는 최대 42자리다. 따라서 이 비트열은 long 타입(64 bit)으로 표시한다.
• 1 이상 $N$ 미만의 모든 수($i$)에 대해 비트열 표현을 구했을 때, $X$의 표현과 다른 자릿수의 개수가 $P$ 이하인 것의 개수를 구한다.
  • ($i$ 비트열) XOR ($X$ 비트열)을 하면 각 자리의 비트가 다른 것만 1이고 나머지는 0인 비트열을 얻는다.
  • 그 비트열의 비트 수를 센다. Long.bitCount() 메소드를 사용하면 된다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer tk = null;

    static final long[] SEG_7 = {
            0b0111111,
            0b0000110,
            0b1011011,
            0b1001111,
            0b1100110,
            0b1101101,
            0b1111101,
            0b0000111,
            0b1111111,
            0b1101111
    };

    public static void main(String[] args) throws Exception {
        tk = new StringTokenizer(rd.readLine());
        int n = Integer.parseInt(tk.nextToken());
        int k = Integer.parseInt(tk.nextToken());
        int p = Integer.parseInt(tk.nextToken());
        int x = Integer.parseInt(tk.nextToken());

        int ret = 0;
        long xFlags = getFlags(x);
        for (int i=1; i<=n; i++) {
            if (i == x)
                continue;   // no flip - skip
            if (Long.bitCount(getFlags(i) ^ xFlags) <= p)
                ret++;
        }

        wr.append(String.valueOf(ret));
        wr.flush();
    }

    static long getFlags(int n) {
        long ret = 0;
        for (int i=0; i<6; i++) {
            ret |= SEG_7[n % 10] << (7 * i);
            n /= 10;
        }
        return ret;
    }
}

메모리 및 시간

• 메모리: 14508 KB
• 시간: 156 ms

리뷰

• 비트 연산의 중요성
• 브루트포스라고 해서 모든 막대기를 켜고 끄는 조합을 완전탐색하는 방법을 생각할 수 있는데, 그럼 경우의 수가 최대 $2^{42}$가 되니 어림도 없다. 조금 더 효율적인 노가다 방법을 찾아야 했다.