[BOJ]18112. 이진수 게임
❌code 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
from collections import deque
def toggle(binary, idx): # idx 위치를 보수로 바꾼 값 반환
binary ^= (1 << idx)
return binary
def binary_game():
q = deque()
q.append(start) # 시작 지점 추가
checked = [-1] * 1024 # 인덱스의 이진수를 만들기 위한 최소 연산 횟수 기록
checked[start] = 0 # 시작 지점 초기화
while True:
cur_num = q.popleft() # 현재 이진수
if cur_num == target: # 목표 이진수 도착
return checked[cur_num]
# 한 자리 숫자를 보수로 바꾸기
for i in range(len(bin(cur_num)) - 3):
result = toggle(cur_num, i)
if 1024 <= result: # 1024 이상의 숫자는 나올 수 없음
continue
if -1 < checked[result]:
continue # 이미 확인한 숫자는 무시
checked[result] = checked[cur_num] + 1 # 연산 횟수 갱신
path[result] += path[cur_num] + [cur_num] # 디버깅용
q.append(result)
# 현재 수에 1 더하기와 현재 수에서 1 빼기
for delta in [-1, 1]:
result = cur_num + delta
if 1024 <= result: # 1024 이상의 숫자는 나올 수 없음
continue
if -1 < checked[result] or result < 0:
continue # 이미 확인한 숫자 또는 음수 무시
checked[result] = checked[cur_num] + 1 # 연산 횟수 갱신
path[result] += path[cur_num] + [cur_num] # 디버깅용
q.append(result)
start = int(input(), 2)
target = int(input(), 2)
print(binary_game())
시도
시작 이진수에서 시작해 만들어지는 모든 이진수를 십진수로 변환하여 checked 리스트에 동일한 값의 인덱스에 연산 횟수를 기록한다.
문제
IndexError
⭕code 2
1
2
3
4
5
6
def binary_game():
q = deque()
q.append(start) # 시작 지점 추가
checked = [-1] * 1000000 # 인덱스의 이진수를 만들기 위한 최소 연산 횟수 기록
checked[start] = 0 # 시작 지점 초기화
시도
시작 이진수에서 목표 이진수로 가는 과정 중 1024 이상의 숫자가 등장할 일이 없다고 생각했기에 code 1에서 리스트의 길이를 1024로 설정했었다. 하지만 code 1에서 인덱스 에러가 발생해 1024 이상의 숫자로 올라간 후 다시 아래로 내려올 때 연산 횟수가 더 작은 경우가 존재할 수도 있다고 생각해 checked 리스트의 길이를 1000000으로 늘렸다. (결과적으로 이는 불필요한 과정이었다.)
문제
특별한 이유 없이 임의의 큰 숫자 1000000을 설정한 것이라 정확하게 필요한 길이를 구하고 싶었다. 시작 이진수에서 목표 이진수로 가는 과정 중 가능한 숫자의 최댓값을 알아내어 해당 최댓값을 통해 길이를 설정하고자 하였다.
⭕code 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
from collections import deque
def toggle(binary, idx): # idx 위치를 보수로 바꾼 값 반환
binary ^= (1 << idx)
return binary
def binary_game():
q = deque()
q.append(start) # 시작 지점 추가
checked = [-1] * 1024
checked[start] = 0 # 시작 지점 초기화
path = [[] for _ in range((1 << 11) + 1)] # 디버깅용 경로 저장 리스트
while True:
cur_num = q.popleft() # 현재 이진수
if cur_num == target: # 목표 이진수 도착
path[cur_num] += [cur_num] # 디버깅용
return checked[cur_num]
for _ in range(3):
# 한 자리 숫자를 보수로 바꾸기
for i in range(len(bin(cur_num)) - 3):
result = toggle(cur_num, i)
if 1024 <= result: # 1024 이상의 숫자는 나올 수 없음
continue
if -1 < checked[result]:
continue # 이미 확인한 숫자는 무시
checked[result] = checked[cur_num] + 1 # 연산 횟수 갱신
path[result] += path[cur_num] + [cur_num] # 디버깅용
q.append(result)
# 현재 수에 1 더하기와 현재 수에서 1 빼기
for delta in [-1, 1]:
result = cur_num + delta
if 1024 <= result: # 1024 이상의 숫자는 나올 수 없음
continue
if -1 < checked[result] or result < 0:
continue # 이미 확인한 숫자 또는 음수 무시
checked[result] = checked[cur_num] + 1 # 연산 횟수 갱신
path[result] += path[cur_num] + [cur_num] # 디버깅용
q.append(result)
start = int(input(), 2)
target = int(input(), 2)
print(binary_game())
시도
시작 이진수에서 목표 이진수까지 만들어지는 과정을 path에 저장하여 이를 확인하였다. 작성한 코드에 오류가 있을 가능성도 있지만 start와 target을 각각 0에서 1023까지 설정하여 path를 기록하였을 때 1024가 등장하는 경우 또는 시작 이진수보다 큰 수를 거쳐 목표 이진수를 만드는 경우 중 2 ** (이진수의 길이) 이상의 값이 등장하는 경우는 찾지 못했다. 시작 이진수보다 큰 수를 거쳐 목표 이진수를 만드는 예시는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# case 1
시작 10111111 # 191
경로 11000000 # 192
목표 10000000 # 128
# case 2
시작 1011111111 # 767
경로 1100000000 # 768
목표 1000000000 # 512
# case 3
시작 10111 # 23
경로 11000 # 24
도착 10000 # 16
# case 4
시작 100111 # 39
경로 101000 # 40
도착 100000 # 32
문제 해결
이를 고려하여 checked의 길이는 1024로 설정하지만 if 문에서 check[result] 값을 확인할 때에 인덱스 에러가 나지 않도록 다음과 같이 코드를 추가하였다.
1
2
3
4
if 1024 <= result: # 1024 이상의 숫자는 나올 수 없음
continue
if -1 < checked[result]:
continue # 이미 확인한 숫자는 무시
요약
- 시작 이진수에서 목표 이진수로 가는 경로에 제시된 최댓값보다 큰 값이 나오는 경우는 발견되지 않았다.
- 따라서 연산 횟수를 기록할 리스트의 길이는 주어진 최댓값으로 충분하며 이를 벗어나는 값은 if 문으로 처리해 인덱스 에러를 방지할 수 있다.
This post is licensed under CC BY 4.0 by the author.