치르보기 빌딩은 1층부터 N층까지 이용이 가능한 엘리베이터가 있다. 엘리베이터의 층수를 보여주는 디스플레이에는 K 자리의 수가 보인다. 수는 0으로 시작할 수도 있다. 0부터 9까지의 각 숫자가 디스플레이에 보이는 방식은 아래와 같다. 각 숫자는 7개의 표시등 중의 일부에 불이 들어오면서 표현된다.
예를 들어 K=4인 경우에 1680층과 501층은 아래와 같이 보인다.
빌런 호석은 치르보기 빌딩의 엘리베이터 디스플레이의 LED 중에서 최소 1개, 최대 P개를 반전시킬 계획을 세우고 있다. 반전이란 켜진 부분은 끄고, 꺼진 부분은 켜는 것을 의미한다. 예를 들어 숫자 1을 2로 바꾸려면 총 5개의 LED를 반전시켜야 한다. 또한 반전 이후에 디스플레이에 올바른 수가 보여지면서 1 이상 N 이하가 되도록 바꿔서 사람들을 헷갈리게 할 예정이다. 치르보기를 사랑하는 모임의 회원인 당신은 호석 빌런의 행동을 미리 파악해서 혼쭐을 내주고자 한다. 현재 엘리베이터가 실제로는 X층에 멈춰있을 때, 호석이가 반전시킬 LED를 고를 수 있는 경우의 수를 계산해보자.
N < 10^K이고 K <= 6이므로 최대 10만 번의 시행 내에 모든 경우를 테스트 가능하다. 브루트포스로 접근해 보자.
현재 층 X와 변화한 층 X'의 각 자리수는 7-segment로 비교해야 한다. 불이 켜진 경우를 1, 꺼진 경우를 0으로 본다면 모든 경우는 2진법으로 표현 가능하고, X[i]와 X'[i]간의 거리는 (두 segment의 XOR시 1의 개수)로 나타낼 수 있다.
이제 위를 기억하고 풀이해본다고 했을때, DFS로 비효율적이게(?) 풀어 볼 수 있다.
풀이 코드(DFS 버전)
num_dict = {
'0' : int('1111110', 2),
'1' : int('0110000', 2),
'2' : int('1101101', 2),
'3' : int('1111001', 2),
'4' : int('0110011', 2),
'5' : int('1011011', 2),
'6' : int('1011111', 2),
'7' : int('1110000', 2),
'8' : int('1111111', 2),
'9' : int('1111011', 2)
}
N, K, P, X = map(int, input().split())
X = list(str(X).rjust(K, '0'))
def dfs(num_list, idx, changed) :
if idx == K :
return 1 if changed and 1 <= int(''.join(num_list)) <= N else 0
next_num_list = num_list[:]
num = num_list[idx]
result = 0
for i in range(10) :
next_num_list[idx] = str(i)
next_changed = bin(num_dict[str(i)] ^ num_dict[num]).count('1') + changed
if next_changed <= P :
result += dfs(next_num_list, idx+1, next_changed)
return result
print(dfs(X, 0, 0))
이 경우는 최종 결과물이 1에서 N사이에 오는지도 검사해야 하므로 꽤 비효율적이다.
..혹은 다음과 같이 1에서 N사이에 오는 모든 값을 검사해보자.
num_dict = {
'0' : int('1111110', 2),
'1' : int('0110000', 2),
'2' : int('1101101', 2),
'3' : int('1111001', 2),
'4' : int('0110011', 2),
'5' : int('1011011', 2),
'6' : int('1011111', 2),
'7' : int('1110000', 2),
'8' : int('1111111', 2),
'9' : int('1111011', 2)
}
N, K, P, X = map(int, input().split())
X_num = X
X = str(X).rjust(K, '0')
result = 0
for i in range(1, N+1) :
target_num = str(i).rjust(K, '0')
tot = 0
for j in range(K) :
tot += bin(num_dict[X[j]] ^ num_dict[target_num[j]]).count('1')
if tot <= P :
result += 1
print(result - 1)
이 경우는 코드는 훨씬 간결해진다만, 실행시간은 실제로 더 오래 걸리는 것을 볼 수 있다. 아마 int to string 변환, rjust 함수의 호출로 인해 조금 오버헤드가 크게 발생하는 것 같다. 어쨌든 두 코드 모두 정상 답안으로 처리되니 취향껏 참고해 도전해보도록 하자.
