백준 2342 Dance Dance Revolution ( 파이썬 / pypy )

문제를 처음 보고 dfs로 풀면 쉽다고 생각했다.

 

그러나 실제로 dfs의 경우 입력이 최대 100,000이므로 시간 초과가 나게된다.

 

결국 dp를 사용해야한다 생각했고, bottom-up 방식으로 풀려했는데 생각이 나지않아서 top-down 방식으로 풀었다.

 

이 과정에서 꽤 많이 생각해야했는데, 반복 함수를 어떤 방식으로 정의할지 생각하는 부분에서 제일 많은 시간이 필요하였다.

 

 

 

이 문제의 경우 solve(n, l, r) 함수를 정의했는데

 

현재 왼쪽발은 l의 위치에, 오른쪽발은 r의 위치에 있으면서 arr[n]까지 밟았을 경우 마지막까지 밟는데 필요한 최소한의 힘으로 정의했다.

 

즉 처음에는  (0, 0, 0)으로 시작하는데

 (0, 0, 0) -> 왼쪽발은 0, 오른쪽발은 0을 밟고있고, arr[0]을 밟아야하는 상태인데 모든 위치를 이동하면 얼마의 힘이 필요한가?

-> min ( solve(1, arr[0], 0) + 왼쪽발로 arr[0]을 밟았을 경우 필요한 힘, solve(1, 0, arr[0]) + 오른쪽발로 arr[0]을 밟았을 경우 필요한 힘)

 

즉 지금 현재 발을 움직여서 다음 단계로 나아갈 때 왼쪽 또는 오른쪽 발을 움직이는 경우밖에 없으며, 한발을 움직이면 전체 밟아야하는 스텝은 하나 줄어들게된다. 

 

이것을 재귀함수로 구현하면 dfs와 비슷하지만 메모이제이션을 통해서 이미 구해진 단계를 재사용하면서 시간을 단축할 수 있었다. 

 

 

import sys
sys.setrecursionlimit(10**6)
 
def move(a, b):
    if a == b:
        return 1
    elif a == 0:
        return 2
    elif abs(b-a)%2 == 0:
        return 4
    else:
        return 3
 
def solve(n, l, r):
    global dp
    if n >= len(arr)-1:
        return 0
 
    if dp[n][l][r] != -1:
        return dp[n][l][r]
 
    dp[n][l][r] = min(solve(n+1, arr[n],r) + move(l, arr[n]), solve(n+1, l, arr[n]) + move(r, arr[n]))
    return dp[n][l][r]
 
arr = list(map(int, sys.stdin.readline().split()))
dp = [[[-1]*5 for _ in range(5)] for _ in range(100000)]
 
print(solve(0, 0, 0))

위에서 나타낸 식을 재귀적으로 구현하였고, 발이 움직이는 경우 필요한 힘을 move함수를 통해 구현해서 쉽게 해결할 수 있었다.