Dance Dance Revolution ( 2342 번 )

2342번: Dance Dance Revolution

 

---

🧠 알고리즘

• 동적 계획법(Dynamic Programming, DP) + 상태 압축 (양발 위치 상태를 기록하는 3차원 DP)

 

✔️ 동작 방식

• 발판 이동 비용을 계산하는 함수 _cr(start, end)를 정의한다.
• DP 배열 dp[i][l][r]를 사용한다.
• 초기 상태는 양발이 중앙(0,0)에 있고 비용 0으로 시작.
• 입력된 스텝 순서를 하나씩 진행
• 마지막 스텝까지 처리한 뒤, 가능한 모든 상태 중 최소 비용을 정답으로 출력한다.

---

 

🧾 코드

import sys

def _cr(start, end):
    if start == 0:
        return 2
    elif start == end:
        return 1
    elif abs(start - end) == 2:
        return 4
    else:
        return 3

def _main(n_list):
    answer = float('inf')
    n_len = len(n_list)
    dp = [[[float('inf')] * 5 for _ in range(5)] for _ in range(n_len)]
    dp[0][0][0] = 0

    for i in range(n_len - 1):
        gogo = n_list[i]
        for l in range(5):
            for r in range(5):
                if dp[i][l][r] == float('inf'):
                    continue

                dp[i + 1][l][gogo] = min(dp[i + 1][l][gogo], dp[i][l][r] + _cr(r, gogo))
                dp[i + 1][gogo][r] = min(dp[i + 1][gogo][r], dp[i][l][r] + _cr(l, gogo))

    for i in range(5):
        for j in range(5):
            answer = min(answer, dp[n_len - 1][i][j])

    return answer

        
n_list = list(map(int, sys.stdin.readline().rstrip().split()))
print(_main(n_list))

---

 

⏱️ 시간 복잡도

dp 크기 : 5 * 5 * n

for i in range(n_len - 1) : 스텝 만큼 순회 ( 선형 시간 복잡도 )
	for l in range(5):
		for r in range(5):
        
해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )