[BOJ] Q2342 Dance Dance Revolution

[BOJ] Q2342 Dance Dance Revolution

Question

Language: Python

Difficulty: Gold 3

해당 문제는 이전 결과값을 저장하여 다음 이동을 수행할때 이전의 결과값을 활용하여 이동거리를 계산하는 방식으로 Dynamic Programming 유형의 문제이다.

dp 배열에 저장될 값은 각각의 index 별로 left,right 일 때의 현재까지 이동 거리를 저장해놓은 상태에서 다음 이동을 수행할때 현재 left 혹은 right 좌표에서 이동을 수행하면 된다. 이런식으로 반복해서 최종적으로 n번째에 도달했을 때 특정 left, right 중에서 가장 최소 이동거리를 구한다.

핵심 로직은 아래와 같다.

for index in range(1,n+1):
    for left in range(5):
        for right in range(5):
            #같은 발이면 이동 X
            if index !=1 and left == right:
                continue                
            next_move=moves[index-1] 

            #왼쪽을 움직이는 경우
            dp[index][next_move][right]=min(dp[index][next_move][right],dp[index-1][left][right]+transitions[left][next_move])

            #오른쪽을 움직이는 경우
            dp[index][left][next_move]=min(dp[index][left][next_move],dp[index-1][left][right]+transitions[right][next_move])

Solution

from math import inf
def solution():
    transitions=[[1]*5 for _ in range(5)]

    #이동 거리 비용 초기화
    for i in range(5):
        for j in range(5):
            if i==j:
                continue

            if i==0:
                transitions[i][j]=2
            
            elif abs(i-j) ==2:
                transitions[i][j]=4
            
            else:
                transitions[i][j]=3
    

    dp=[[[inf] *5 for _ in range(5)] for _ in range(n+1)]
    dp[0][0][0]=0

    for index in range(1,n+1):
        for left in range(5):
            for right in range(5):
                #같은 발이면 이동 X
                if index !=1 and left == right:
                    continue                
                next_move=moves[index-1] 

                #왼쪽을 움직이는 경우
                dp[index][next_move][right]=min(dp[index][next_move][right],dp[index-1][left][right]+transitions[left][next_move])

                #오른쪽을 움직이는 경우
                dp[index][left][next_move]=min(dp[index][left][next_move],dp[index-1][left][right]+transitions[right][next_move])
            



    min_distance=inf
    for left in range(5):
        for right in range(5):
            min_distance=min(min_distance,dp[n][left][right])

    print(min_distance)
            
if __name__ == "__main__":
    moves=list(map(int,input().split()))
    moves.pop()
    n=len(moves)
    solution()

Solution 2

해당 풀이를 반복문 대신 재귀문을 활용할 수 있다.

from math import inf
import sys
def initiate_transitions():
    transitions=[[1]*5 for _ in range(5)]

    #이동 거리 비용 초기화
    for i in range(5):
        for j in range(5):
            if i==j:
                continue

            if i==0:
                transitions[i][j]=2
            
            elif abs(i-j) ==2:
                transitions[i][j]=4
            
            else:
                transitions[i][j]=3
    return transitions
    
def solution(index, left,right):
    global dp
    if index == n:
        return 0
    if dp[index][left][right] != -1:
        return dp[index][left][right]

    next_move=moves[index]
    dp[index][left][right]=min(solution(index+1,left,next_move) + transitions[right][next_move], solution(index+1,next_move,right) + transitions[left][next_move])
    return dp[index][left][right]
            
if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    moves=list(map(int,input().split()))
    moves.pop()
    n=len(moves)

    transitions=initiate_transitions()

    dp=[[[-1] * 5 for _ in range(5)] for _ in range(n+1)]
    print(solution(0,0,0))