백준 빌런 호석(22251)

빌런 호석

1. 힌트

1) $K \le 6$이기 때문에 가능한 LED의 표현은 $10^6$보다 작습니다.

2) $u$층의 표현을 $v$층으로 바꾸려면 몇 번 반전시켜야 하는지는 각각의 자리수를 비교하면 쉽게 알 수 있습니다.

3) $0$에서 $9$까지 숫자를 다른 숫자로 바꾸는데 필요한 반전 횟수를 미리 구해두면 편하게 구현할 수 있습니다.

2. 접근

1) 순서를 강제할 수 있을까?

어렵게 생각하면 그래프 탐색을 통해서 방문가능한 정점(표현)을 찾는 것으로 생각할 수 있는데, $u$층의 표현을 $v$층으로 바꾸는데 드는 비용은 언제나 일정한 것을 생각하면 일일히 반전시키는 순서를 고려하지 않고, $1$부터 $10^6$까지의 완전탐색으로 구현할 수 있습니다.

3. 구현

public class Main {
	
	static final int[] LED = 
	{ 0b1110111, 
	0b0010010, 
	0b1011101, 
	0b1011011, 
	0b0111010, 
	0b1101011, 
	0b1101111, 
	0b1010010, 
	0b1111111, 
	0b1111011 };
	
	static int[][] adj = new int[10][10];
	
	static {
		for (int i = 0; i <= 9; i++)
			for (int j = i + 1; j <= 9; j++)
				adj[i][j] = adj[j][i] = Integer.bitCount(LED[i] ^ LED[j]);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int P = Integer.parseInt(st.nextToken());
		int X = Integer.parseInt(st.nextToken());
		int cnt = 0;
		for (int Y = 1; Y <= N; Y++) {
			// X -> Y를 만들 수 있는지 확인
			int cost = 0; 
			int temp1 = X; int temp2 = Y;
			for (int i = 0; i < K; i++) {
				cost += adj[X % 10][Y % 10];
				X /= 10; Y /= 10;
			}
			X = temp1; Y = temp2; 
			if (1 <= cost && cost <= P) cnt++;
		}
		System.out.println(cnt);
	}

}