[BOJ] 2342번 : Dance Dance Revolution(DP)

목차

접근

D.P.로 해결하는 간단한 문제. 근데 생각지도 못한 완전탐색을 진행하면서..

너무 당연한 형태의 D.P.문제여서 그냥 풀면되겠지 했는데, 생각보다 점화식이 떠오르지 않았다.

왼발과 오른발에 대한 얘기가 있어서 어떻게 접근하지 하면서, 질문게시판 제목들을 보면서 대충 풀이를 유추했는데 시간복잡도에 관한 질문들이 많이 보였다. 그럼 혹시...? 하면서 전체탐색을 진행하며 D.P.를 수행하여 해결했다.

 

해결

이번에 밟아야할 발판에 대해서, (왼발, 오른발) 모든 조합에 대한 경우의 수를 탐색하며 D.P.를 수행했다.

이렇게 전체 탐색에 대한 의심을 한 이유는 입력의 길이가 100,000개 까지 들어올 수 있다는 것, (왼발, 오른발)의 조합이 5 x 5 = 25가 나옴으로 최대 시간복잡도는 `O(25 * 100,000)` 이 될 수 있기 때문에였다.

제출하고 이 정도는 시간초과가 나지 않나보다. 신기했다.

 

코드

import sys

input = sys.stdin.readline

N = list(map(int, input().split()))
len_N = len(N)
steps = [[[float('inf') for _ in range(5)] for _ in range(5)] for _ in range(len_N)] # (len_N, 5, 5)
steps[0][0][0] = 0

def calc_distance(a, b): # a부터 b까지의 거리
    if a == 0: # 중앙에서 다른데로 움직이면 무조건 2의 힘
        return 2
    elif a == b: # 둘이 같은 위치로 움직이면 1의 힘
        return 1
    elif abs(b - a) == 2: # 반대편의 위치러 움직이면 4의 힘
        return 4
    else: # 그 외 인접한 지역은 3의 힘
        return 3
    
    
for i, v in enumerate(N):
    if not v:
        break
    
    # 전체 케이스에 대해서 움직임 힘 최솟값 계산
    for l in range(5):
        for r in range(5):
            steps[i+1][l][v] = min(steps[i+1][l][v],
                                   steps[i][l][r] + calc_distance(r, v)) # 왼쪽발은 가만히 있고, 오른쪽 발이 이동할 때
            
            steps[i+1][v][r] = min(steps[i+1][v][r],
                                   steps[i][l][r] + calc_distance(l, v)) # 오른쪽발은 가만히 있고, 왼쪽 발이 이동할 때
            
min_step = min([min(step) for step in steps[-1]])
print(min_step)