[Silver II] 이상한 하노이 탑 - 15500

문제 링크

성능 요약

메모리: 32276 KB, 시간: 52 ms

분류

자료 구조, 구현, 시뮬레이션, 스택

문제 설명

승민이는 기존 하노이 탑 문제를 약간 변형한 이상한 하노이 탑 문제를 만들었다.

이상한 하노이 탑 문제와 기존 하노이 탑 문제와 다른 점이 2가지가 있는데 하나는 "쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.(중간 과정 역시 그래야함)" 라는 조건이 삭제되었다는 점이고 또 다른 하나는 첫 번째 장대에 원판들이 반경 상관없이 무작위로 배치되어 있다는 점이다.

승민이는 이 문제를 진수에게 주었고 원판을 옮긴 횟수가 12345보다 같거나 작으면 피자를 사주기로 하였다. 진수를 도와 피자를 먹게 해주자!

입력

첫 번째 줄에는 원판의 개수 N (1 ≤ N ≤ 123) 이 주어진다.

두 번째 줄에는 첫 번째 장대에 있는 원판들의 반경 나타내는 정수 ai (1 ≤ ai ≤ N) 들이 공백을 두고 주어진다. (제일 아래에 있는 원판의 반경부터 주어진다.)

출력

첫 번째 줄에 원판을 옮긴 횟수 K (0 ≤ K ≤ 12345) 를 출력한다.

다음 K 개 줄에 걸쳐 A B (1 ≤ A, B ≤ 3) 를 출력하는데 A 번째 장대 맨위에 있는 원판 하나를 B 번째 장대 맨위로 옮긴다는 뜻이다.

---

풀이

아이디어

몇번 움직여보니까 필요한 전체 로직의 흐름은 다음과 같다.

• 처음은 1번 bar에서 시작한다
• 1번 bar에서 2번 bar로 원판을 옮긴다
• 이때 원판의 크기를 $n$부터 역순으로 선택하여 3으로 옮긴다
• 그렇지 않은것은 1번 bar에 있다면 2번으로 반대라면 반대의 과정으로 옮긴다

코드 구현은 간단하다. (재귀를 이용하였다.)

코드

n = int(input())
m = int(n)

s1, s2 = [list(map(int, input().split())), 1], [[],2]
c = []

def solve(select, to):
    global m
    empty = lambda x: len(x) == 0

    if empty(select[0]) and empty(to[0]):
        return
    
    while not empty(select[0]):
        p = select[0].pop()

        if p == m:  # 찾는 수가 나오면 3으로 이동
            m -= 1
            c.append([select[1], 3])
            
        else:
            to[0].append(p)
            c.append([select[1], to[1]])
    
    solve(to, select)

solve(s1, s2)

print(len(c))
for i in c:
    print(*i)

---

회고

간단한 문제인데 몇개의 반례처리를 생각못해서 약간의 실수가 있었던 문제