[백준] 2342. Dance Dance Revolution - 파이썬

[Gold III]

 

https://www.acmicpc.net/problem/2342

2342번: Dance Dance Revolution

 

풀이 1

DP 문제라는 것은.. 보자마자 알겠음.

[백준] 2281. 데스노트 가 생각이 나, 비슷한 방식으로, Top-Down 방식으로 풀려고 시도했으나..

line 12~13 부분에서 2의 제곱 형식으로 recursion이 계속 생길 거라.. 당연히 MLE나 TLE가 날 것이라고 예상했음.

TLE.

import sys
sys.setrecursionlimit(10**5)
nums = [*map(int, input().split())]

dp = [4*len(nums)] * (len(nums)-1)


def move(i, feet):
    if i >= len(nums)-1:
        return 0

    dp[i] = min(move(i+1, (feet[0], nums[i])) + po(feet[1], nums[i]),
                move(i+1, (nums[i], feet[1])) + po(feet[0], nums[i]))

    return dp[i]


def po(a, b):
    if a == 0:
        return 2
    elif a == b:
        return 1
    elif abs(a-b) == 2:
        return 4
    else:
        return 3


move(0, (0, 0))
print(dp[0])

 

풀이 2

계속 머리를 굴리며 수정해보다가.. 이 방법으로는 도저히 답이 나올 것 같지 않아 방향을 전환하기로 함.

Bottom-Up 방식으로 가는 게 낫겠다 싶었고, LCS 문제와 비슷한 방식으로 접근해보면 되지 않을까? 라고 생각함.

dp[i][j] 같이 2차원 배열로 저장하는 것이 아닌, dp[i][left][right] 와 같이 i번째, 왼발(0~4), 오른발(0~4)에 대해 저장해 나가면서.. Memoization을 이용해 시간 단축. (결국은 모든 경우의 수를 탐색하게 되는 것이긴 함.)

 

이 dp 3차원 배열의 크기는 입력되는 수열의 길이는 100,000을 넘지 않으므로, 100000*5*5 = 2,500,000 - 250만.

250만개 정도는 모두 계산하더라도, Time Limit에 걸리지 않을 것이라 생각했음.

 

line 20~27에서 볼 수 있듯, 한 원소 당 2번의 연산.. 총 최대 500만번의 연산이 이루어졌음.

(길이 i의 입력이 들어왔을 때, i*50회이므로, Time complexity는 O(N))

다음 step의 번호를 a라 할 때, 모든 원소에 대해 순회를 돌며, dp[i][left][right] 에서

dp[i+1][a][right] 와 dp[i+1][left][a] 를 갱신해 나가며 반복!

 

AC.

nums = [*map(int, input().split())]

# dp[i][left][right] = Minimum of Sum of power - [ith][left foot][right foot]
dp = [[[4*len(nums) for _ in range(5)] for _ in range(5)]
      for _ in range(len(nums))]
dp[0][0][0] = 0


def po(a, b):
    if a == 0:
        return 2
    elif a == b:
        return 1
    elif abs(a-b) == 2:
        return 4
    else:
        return 3


for i in range(len(dp)-1):
    a = nums[i]
    for left in range(5):
        for right in range(5):
            dp[i+1][left][a] = min(dp[i+1][left][a], dp[i]
                                   [left][right] + po(right, a))
            dp[i+1][a][right] = min(dp[i+1][a][right],
                                    dp[i][left][right] + po(left, a))

print(min(map(min, dp[len(dp)-1])))

 

번외

풀이 1과 같이, Top-Down 방식으로 접근하되,

dp[i][left][right] 3차원 배열에 memoization을 써 가며 풀이하는 것도 된다고 한다!

결국 dp[i][left][right] 와 같은 형식으로 memoization 하는 것을 생각해내는 것이 관건이였던 문제.