백준 22251 - 빌런 호석

문제

https://www.acmicpc.net/problem/22251

풀이

문제의 조건에서 관건이 되는 부분은 다음 2가지였다.

• 디스플레이를 어떤 형태로 표현하여 숫자를 디스플레이로 변환할 것인지?
• 모든 디스플레이를 다 껐다 켜보며 경우를 구할 경우 시간복잡도가 기하급수적으로 상승할 텐데 탐색을 어떤 식으로 진행할 지?

우선 조건에 주어진 형태에서 디스플레이는 7개의 LED를 가진다. 따라서 boolean[7] 의 형태로 각 LED 별로 번호를 매겨 표현하였다.

0~9까지의 숫자는 미리 이 boolean[7] 타입으로 표현하여 숫자→디스플레이 변환이나 비교 등에 사용하도록 저장해두었다. 이에 따라 엘리베이트의 층수는 boolean[K][7] 구조로 표현하였다.

다음 관건은 경우의 수를 어떻게 구할 것이냐 였다. 이는 아주 간단한 접근의 전환을 통해 구현할 수 있었는데 아래 절차를 따라 로직을 구성하였다.

1. 바꾸고자 하는 범위인 $1\sim N$의 범위를 탐색한다. 유의할 점은 $X$가 포함될 경우 제외해야 한다.
2. 바꾸고자 하는 층수를 디스플레이(boolean[K][7]) 형태로 변환한다.
3. 현재 층과 바꾸고자 하는 층의 디스플레이를 비교하여, 반전해야 할 LED 개수를 구한다.
4. 이 개수가 $1\sim P$의 범위 내면 반전 가능한 경우의 수로 카운팅해준다.

디스플레이를 비교해주는 로직들의 경우 배열의 크기가 정해져 있어 사실상 상수 시간에 가까으므로 전체 로직의 시간복잡도는 $O(N)$으로 수렴한다. 따라서 $N=10^6$인 최악의 경우에도 무난히 제한 조건 1초를 통과할 수 있다.

코드

import static java.lang.Integer.*;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static boolean[][] numbers;
	static int N, K, P, X;

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

		initNumbers();
		boolean[][] display = convertNumberToDisplay(X);
		int result = 0;
		for (int i = 1; i <= N; i++) {
			if (i == X)
				continue;

			boolean[][] floorDisplay = convertNumberToDisplay(i);

			int count = findDiffCount(floorDisplay, display);

			if (count < 1 || count > P)
				continue;
			result++;
		}

		System.out.println(result);
		br.close();
	}

	static void initNumbers() {
		numbers = new boolean[10][7];
		numbers[0] = new boolean[] {true, true, true, false, true, true, true};
		numbers[1] = new boolean[] {false, false, true, false, true, false, false};
		numbers[2] = new boolean[] {false, true, true, true, false, true, true};
		numbers[3] = new boolean[] {false, true, true, true, true, true, false};
		numbers[4] = new boolean[] {true, false, true, true, true, false, false};
		numbers[5] = new boolean[] {true, true, false, true, true, true, false};
		numbers[6] = new boolean[] {true, true, false, true, true, true, true};
		numbers[7] = new boolean[] {false, true, true, false, true, false, false};
		numbers[8] = new boolean[] {true, true, true, true, true, true, true};
		numbers[9] = new boolean[] {true, true, true, true, true, true, false};
	}

	static boolean[][] convertNumberToDisplay(int number) {
		boolean[][] display = new boolean[K][7];
		int i = display.length - 1;
		while (number > 0) {
			int place = number % 10;
			System.arraycopy(numbers[place], 0, display[i--], 0, 7);
			number /= 10;
		}
		while (i >= 0) {
			System.arraycopy(numbers[0], 0, display[i--], 0, 7);
		}
		return display;
	}

	static int findDiffCount(boolean[][] number, boolean[][] display) {
		int count = 0;
		for (int i = 0; i < K; i++) {
			for (int j = 0; j < 7; j++) {
				if (number[i][j] == display[i][j])
					continue;

				count++;
			}
		}

		return count;
	}
}

결과