23240번 - Colorful Tower of Hanoi 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB | 302 | 119 | 98 | 38.431% |
문제
이 문제는 잘 알려진 하노이 탑 문제의 변형이다.
하노이 탑 문제는 다음과 같다. 세 개의 막대기, 즉 막대기-1, 막대기-2, 막대기-3 이 있고, 막대기1 에 크기가 다른 $n$ 개의 디스크가 내림차순으로 쌓여 있다. 즉, 가장 작은 디스크가 가장 위에, 가장 큰 디스크가 가장 아래에 놓여 있다. 문제의 목표는 막대기-1 에 쌓여 있는 모든 디스크를 막대기-3 으로 옮기는 것이다. 단, 옮기는 과정에서, 한 번에 하나의 디스크만 옮길 수 있으며, 어떤 경우에도 큰 디스크가 작은 디스크 위에 놓여서는 안 된다.
원래의 하노이 탑 문제가 아래와 같이 변형된다.
- 동일한 크기의 디스크가 허용된다. 따라서 디스크를 이동하는 과정에서 어떤 디스크는 크기가 동일하거나 또는 더 큰 디스크 위에 놓을 수 있다.
- 각 디스크는 빨간색(
R), 녹색(G) 또는 파란색(B)의 세 가지 색상 중 하나로 칠해져 있다. 하지만, 동일한 크기의 디스크는 동일한 색상을 가진다. - 동일한 크기의 디스크가 둘 이상일 경우, 디스크를 옮긴 후 이들 간의 상대적 순서가 유지될 수도 있고, 반대로 될 수 있는데, 이를 디스크 색이 결정한다. 즉, 디스크 색이 빨간색이면 모든 디스크를 최종적으로 이동한 후 동일한 크기의 디스크의 상대적인 순서가 반대로 되어야 한다. 디스크의 색이 파란색이면 모든 디스크의 이동이 완료된 후의 상대적인 순서가 처음의 순서와 동일해야 한다. 그리고 색이 녹색이면 이동 후의 상대적인 순서가 중요하지 않다. 다만, 디스크를 이동시키는 중간 과정에서는 상대적인 순서에 대한 조건을 만족할 필요는 없다.
- 디스크 이동의 총 횟수를 최소화해야 한다.
그림 C.1 은 디스크를 모두 옮긴 후, 크기가 같은 디스크의 색상에 따른 상대적 순서의 조건을 만족시키는 예를 보여준다.
그림 C.1
입력
입력은 표준입력을 사용한다. 첫 번째 줄에는 정수 $m$ ($1 \le m \le 25$)이 주어진다. 여기서, $m$은 가장 큰 디스크의 지름을 나타낸다. 이어지는 $m$ 줄에서, $i$ ($1 \le i \le m$) 번째 줄에는 하나의 영어 대문자와 정수 $𝑘$ ($\ge 1$)가 주어지는데, 이는 지름의 크기가 $i$ 인 디스크에 관한 정보를 나타낸다. 즉, 영어 대문자는 디스크의 색을, 정수 $k$는 동일한 크기의 디스크 개수를 나타낸다. 문자 ‘R’은 빨간색, ‘G’는 녹색, ‘B’는 파란색을 각각 의미한다. $1$부터 $m$까지의 디스크 지름 각각에 대해서, 그 지름을 가진 디스크가 적어도 하나 이상 존재한다.
참고로, 쌓여 있는 디스크의 총 개수는 50 을 넘지 않는다.
출력
출력은 표준출력을 사용한다. 결과를 한 줄에 출력하되, 디스크의 색에 따른 상대적인 순서의 조건을 만족시키면서 막대기-1 에 쌓여 있는 모든 디스크를 막대기-3 으로 이동하기 위한 최소 이동 횟수를 출력한다.
예제 입력 1
2 R 1 B 3
예제 출력 1
9
예제 입력 2
3 G 1 B 2 R 3
예제 출력 2
11
예제 입력 3
5 G 2 R 3 R 2 G 3 B 3
예제 출력 3
120
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호