[python] 프로그래머스 - 하노이의 탑

출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12946

프로그래머스

 

얼씨구나 dp구나 하고 들어왔는데 당황...

 

 

먼저, 생각해야 할 부분

 

1. 하노이의 탑은 1번 막대에서 3번 막대로 원판을 이동시키는 것이다.

     기존 하노이의 탑 문제에서는 n개의 원판을 1번으로 3번으로 이동시키기 위한 이동 횟수를 물어봤다면,

     여기서는 이동방법을 리스트로 return하는 조금 변형된 유형인데 핵심은 같다.

    

    기존 하노이의 탑에서 이동 횟수를 구할 때를 생각해보자.

   

    1. 가장 큰 원판을 제외한 나머지를 2번으로 옮긴다. (n)

    2. 가장 큰 원판을 3번으로 옮긴다. (1)

    3. 2번으로 옮겼던 원판을 다시 3번으로 옮긴다. (n)

 

    따라서 2n + 1이라는 점화식이 나오게 된다. 이 유형도 비슷하다.

    가장 마지막 원판을 제외한 나머지를 시작 막대 1번에서 목적 막대 3번으로 옮기는 방법에서 도움 막대가 2번이었다면,

    시작 막대 1번에서 목적 막대 2번으로 옮기기 위해서는 도움 막대가 3번이 될 뿐이다. (위의 1, 2, 3 중 1에 해당)

 

---

 

풀이

 

# n = 1 : [1, 3] 1 -> 3으로 옮기는 과정

# n = 2 : [1, 2], [1, 3], [2, 3] 1 -> 3으로 옮기는 과정

# [1, 3], [1, 2], [3, 2] 1 -> 2로 옮기는 과정 : 3을 2로 2를 3으로
# [2, 1], [2, 3], [1, 3] 2 -> 3으로 옮기는 과정 : 1을 2로 2룰 1로

# n = 3 : [1, 3], [1, 2], [3, 2], [1, 3], [2, 1], [2, 3], [1, 3] : 합체

# dp 문제

def solution(n):
    answer = [[]]
    
    dp = [[] for _ in range(n + 1)]

    dp[1] = [[1, 3]]
    
    for i in range(2, n + 1):
        left_arr_list = []
        right_arr_list = []
        
        for k, v in dp[i-1]:
            a, b = k, v
            
            if k == 3:
                a = 2
            elif k == 2:
                a = 3
            
            if v == 3:
                b = 2
            elif v == 2:
                b = 3
                
            left_arr_list.append([a, b])
        
        for k, v in dp[i-1]:
            a, b = k, v
            
            if k == 1:
                a = 2
            elif k == 2:
                a = 1
            
            if v == 1:
                b = 2
            elif v == 2:
                b = 1
                
            right_arr_list.append([a, b])
        
        dp[i] = left_arr_list + [[1, 3]] + right_arr_list
        
    return dp[n]

 

---

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들