[백준] 2342 - Dance Dance Revolution

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

2342번: Dance Dance Revolution

solved.ac의 class5 문제를 보던 중 시도해보게 된 DP 문제 Dance Dance Revolution의 풀이과정을 정리한다.

매우 비효율적으로 풀게 되었지만, 우선은 3차원 DP테이블로 DP문제를 푸는 경험을 해봤다는 것으로 만족하고자 한다.

 

이 문제를 보고 제일 먼저 떠오른 풀이는 그리디하게 매 순간 가장 가까운 위치의 버튼을 누르는 것이었지만,

지금 당장 누르지 않고 참았다가 다른 것을 누르는 것이 더 효율적일 때도 있다.

 

1 3 2 4 1 2 0

라는 예시가 있을 때,

맨 처음 2를 누른 발은 마지막 2를 누르기 위해 기다려야만 최적해인 14의 힘으로 버튼을 누를 수 있다.

 

이때 주어지는 수열의 길이가 최대 10만으로 다소 작은 사이즈인 점을 고려해볼 때

DP로 풀면 풀릴 것 같다는 느낌은 바로 받을 수 있었다.

---

풀이 아이디어

이제 점화식을 세우는 것이 관건인데 왼발과 오른발을 모두 고려하여야하고,

각 발이 마지막으로 누른 위치에 따라 다음 위치를 누를 때 추가되는 점수가 다른 점에서

왼발과 오른발 각각이 마지막으로 누른 버튼위치에 따른 점수를 기록하면 되겠다는 아이디어를 떠올렸다.

 

그래서 dp테이블은 다음과 같이 구성하였고

dp[현재 스탭 인덱스][왼발최종위치][오른발최종위치]

 

점화식은 다음과 같이 구성하였다.

dp[현재 스탭 인덱스][왼발최종위치][오른발최종위치] =

dp[직전 스탭 인덱스][왼발최종위치]오른발최종위치] + 이동하여 버튼을 누르는데 든 힘

 

만약 1을 누를 차례라면

dp[현재스탭인덱스][1][직전 오른발최종위치]

dp[현재스탭인덱스][직전 왼발최종위치][1]

이 두가지를 각각 구하여 저장해두면 된다.

---

최종 코드

# 2342 Dance Dance Revolution
seq = list(map(int, input().split()))
seq = [0] + seq
dp = [[[500000 for _ in range(5)] for __ in range(5)] for ___ in range(len(seq))]
dp[0][0][0] = 0

for i in range(1, len(seq)):
    if seq[i] == 0:  # print answer
        answer = 500000
        for left in range(5):
            for right in range(5):
                if left == right:
                    continue
                if dp[i-1][left][right] == -1:
                    continue
                if left == seq[i-1] or right == seq[i-1]:
                    answer = min(answer, dp[i-1][left][right])
        print(0 if answer == 500000 else answer)
        break

    now_step = seq[i]

    for left in range(5):
        for right in range(5):
            if dp[i-1][left][right] == -1:
                continue

            if left != now_step: # 왼발은 고정시키고, 오른발을 now_step으로 이동시키는 경우
                if right == 0:
                    dp[i][left][now_step] = min(dp[i][left][now_step], dp[i-1][left][right] + 2)
                elif abs(now_step - right) == 0: # 같은 위치를 밟는 경우
                    dp[i][left][now_step] = min(dp[i][left][now_step], dp[i-1][left][right] + 1)
                elif abs(now_step - right) == 1 or abs(now_step - right) == 3: # 인접한 곳을 밟는 경우
                    dp[i][left][now_step] = min(dp[i][left][now_step], dp[i-1][left][right] + 3)
                elif abs(now_step - right) == 2: #  반대편으로 움직이는 경우
                    dp[i][left][now_step] = min(dp[i][left][now_step], dp[i-1][left][right] + 4)

            if right != now_step:  # 오른발은 고정시키고, 왼발을 now_step으로 이동시키는 경우
                if left == 0:
                    dp[i][now_step][right] = min(dp[i][now_step][right], dp[i - 1][left][right] + 2)
                elif abs(now_step - left) == 0:  # 같은 위치를 밟는 경우
                    dp[i][now_step][right] = min(dp[i][now_step][right], dp[i - 1][left][right] + 1)
                elif abs(now_step - left) == 1 or abs(now_step - left) == 3:  # 인접한 곳을 밟는 경우
                    dp[i][now_step][right] = min(dp[i][now_step][right], dp[i - 1][left][right] + 3)
                elif abs(now_step - left) == 2:  # 반대편으로 움직이는 경우
                    dp[i][now_step][right] = min(dp[i][now_step][right], dp[i - 1][left][right] + 4)

이 코드의 dp 테이블을 출력해보면

왼발, 오른발로 구성된 2차원 행렬이 대각선 대칭임을 알 수 있다.

이는 첫 발을 밟을 때, 왼발을 먼저 밟든 오른발을 먼저 밟든 상관이 없는데,

이 코드에서는 둘을 구분하여 저장하기 때문에 생기는 문제이다.

만약 첫 발 한정으로 왼발 오른발을 구분하지 않는다면 시간효율이 더 좋아질 것으로 생각된다.