[BOJ 23240, Python 3] Colorful Tower of Hanoi
https://www.acmicpc.net/problem/23240
23240번: Colorful Tower of Hanoi
입력은 표준입력을 사용한다. 첫 번째 줄에는 정수 $m$ ($1 \le m \le 25$)이 주어진다. 여기서, $m$은 가장 큰 디스크의 지름을 나타낸다. 이어지는 $m$ 줄에서, $i$ ($1 \le i \le m$) 번째 줄에는 하나의 영
www.acmicpc.net
ICPC 2021 예선전에 나온 문제이다. 내가 맡아서 풀은 문제인데 대회 당시 분명 풀이가 맞지만 다른 예외사항을 찾지 못한 것 같아서 맞왜틀이 나와 결국 풀지 못한채로 끝났다. 지금 다시 풀어보니까 예외 사항 하나를 찾아서 풀었음
대회에서 풀었으면 등수가 거의 (현재 등수) / 2 수준으로 뛰어 올랐을텐데 참 많이 아쉽다.
풀이
일단 한 층마다 색깔도 같고, 크기가 같지만, 숫자가 다른 디스크가 여러 개 있는데, 이런 디스크들의 묶음을 하나의 디스크로 치환해서 문제를 풀려고 하면 일반적인 하노이탑 형태가 보이게 된다.
그리고 색깔마다 이동횟수가 다르다고 문제에 적혀있는데 자세한 방식을 알아보자.
- 모든 색깔의 디스크들은 한 번 이동할 경우 같은 층의 디스크 번호의 순서가 반대로 뒤집어진다.
- 초록색(G)은 이동후의 순서가 중요하지 않으므로 한 번 이동으로 끝낼 수 있다.
- 파란색(B)은 현재까지 이동한 횟수가 홀수인 경우엔 한 번만 3번 고리로 이동하면 끝나지만, 현재까지 이동한 횟수가 짝수인 경우에는 1번 고리나 2번 고리에 존재할 것이다. 그러면 1번 고리에 있으면 2번 고리로, 2번 고리에 있으면 1번 고리로 이동시킨 뒤 3번 고리로 이동 해야한다. 그러면 B는 조건을 충족한 채로 3번 고리로 이동할 수 있게 된다.
- 빨간색(R)은 파란색과 비슷하게 이동한 횟수가 짝수인 경우엔 한 번만 3번 고리로 이동하면 끝나지만, 홀수인 경우에는 이동을 최소 한 번 했으므로 1번 고리나 2번 고리에 존재할 것이다. 그러면 1번, 2번 고리중 이동할 수 있는 고리로 이동시킨 뒤 3번 고리로 이동해야한다. 그러면 R은 조건을 충족한 채로 3번 고리로 이동할 수 있게 된다.
나머지는 일반 하노이탑 형식대로 이동하면 된다.
예제 1번을 살펴보자
- B 3을 이동해야 하는데, 현재 B의 이동횟수가 0번이므로 2번 고리로 이동 후 3번 고리로 이동해야 한다.
- R을 1번 고리에서 3번 고리로 이동함(총 이동 횟수 1회)
- B를 1번 고리에서 2번 고리로 이동함(총 이동 횟수 4회)
- R을 3번 고리에서 1번 고리로 이동함(총 이동 횟수 5회)
- B를 2번 고리에서 3번 고리로 이동함(총 이동 횟수 8회)
- 이제 1번 고리에 있는 R을 3번 고리로 이동해야 하는데, R의 이동 횟수가 2회이므로 짝수이니 바로 3번 고리로 이동시켜주면 된다.(총 이동 횟수 9회)
예제 2번도 살펴보자. 여기서는 각 층마다 기록횟수를 저장해둘 것이다.
- R 3을 이동해야 하는데, 현재 R의 이동횟수가 0번이므로 바로 3번 고리로 이동하면 된다.
- G 1의 이동 횟수 2회
- B 2의 이동 횟수 1회
- R 3의 이동 횟수 1회
- 총 이동 횟수는 (1 * 2) + (2 * 1) + (3 * 1) = 7회
- B 2를 이동해야 하는데, B 2의 이동횟수가 1회이므로 홀수이니 바로 3번 고리로 이동해줄 수 있다.
- G 1의 이동 횟수 1회
- B 2의 이동 횟수 1회
- 총 이동 횟수는 7 + (1 * 1) + (2 * 1) = 10회
- G 1을 이동해야 하는데, 이건 순서가 상관없으므로 바로 3번 고리로 이동해줄 수 있다.
- G 1의 이동 횟수 1회
- 총 이동 횟수는 10 + (1 * 1) = 11회
이렇게 하면 예제 3번도 짧게 바로 구할 수 있게 된다.
이제 여기에 예외사항이 두 가지가 존재한다.
- 한 층에 디스크가 1개 있을 경우
이 부분은 색깔과 관계 없이 바로 3번 고리로 이동해주면 된다. - 맨 위에 있는 층의 디스크들에 대한 이동 횟수 처리
맨 윗층의 디스크의 색깔이 G인 경우엔 순서를 고려하지 않으므로 바로 3번 고리로 넘겨주면 되지만, 색깔이 파란색이나 빨간색인 경우에는 각각 짝수일 때, 홀수일 때 두 번씩 움직여야 한다.
두 번씩 움직여야할 때는 다른 층에서 두 번 움직일 때처럼 (디스크의 갯수) * 2회만큼 움직이는게 아니라 (디스크의 갯수) * 2 - 1회만큼 움직이면 된다.
왜냐하면 맨 아래에 둘 디스크는 두 번 움직일 필요없이 3번 고리로 넘겨주면 되기 때문이다.
그래서 이 예외사항까지 잘 처리하면 문제를 풀 수 있게 된다.
대회에서 예외사항 2번을 생각지도 못했는데, 팀원들한테 좀 더 자세히 알려주고 대회 끝나기 전까지 여기에 시간을 투자했어야 했는지 여러가지 생각이 든다.
코드
코드가 원래 C++ 코드를 그대로 가져온거라 줄일 수 있는 부분이 많이 남아 있습니다.
|
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
|
m = int(input())
arr = [input().split() for i in range(m)]
color = [] # 색깔을 저장한 배열
val = [] # 한 층에 디스크가 몇 개 있는지 저장한 배열
move = [0] * m # 한 층의 이동 횟수
ans = 0
for i in range(m):
color.append(arr[i][0])
val.append(int(arr[i][1]))
for i in range(m-1, -1, -1):
if color[i] == 'G':
move[i] += 1
for j in range(i-1, -1, -1):
move[j] += 2 ** (i - j - 1)
elif color[i] == 'B': # 현재 move가 짝수인 경우 두 번 이동해야함. 홀수면 한 번 이동해야함
if move[i] % 2 == 0 and val[i] != 1: # 예외사항 1번 처리
if i == 0: ans -= 1 # 예외사항 2번 처리
move[i] += 2
for j in range(i-1, -1, -1):
move[j] += 2 ** (i - j)
else:
move[i] += 1
for j in range(i-1, -1, -1):
move[j] += 2 ** (i - j - 1)
else: # 현재 move가 짝수인 경우 한 번 이동해야함. 홀수면 두 번 이동해야함
if move[i] % 2 == 0 or val[i] == 1: # 예외사항 1번 처리
move[i] += 1
for j in range(i-1, -1, -1):
move[j] += 2 ** (i - j - 1)
else:
if i == 0: ans -= 1 # 예외사항 2번 처리
move[i] += 2
for j in range(i-1, -1, -1):
move[j] += 2 ** (i - j)
for i in range(m):
ans += val[i] * move[i]
print(ans)
|
cs |