[백준] [Python] 2342 Dance Dance Revolution

문제

백준 2342 Dance Dance Revolution

풀이

나는 처음에 문제 이해가 막막해서 되게 복잡한 방법으로 풀었지만, DP구조만 잘 이해하면은 되게 간단하게 풀 수 있다.

우선 기본 아이디어부터 생각해보자. 지시 사항이 1~4중의 숫자로 주어졌을 때 두 발 중 한 발은 지시한 숫자를 밟고 있어야 한다. 다른 한 쪽 발은? 같은 칸에만 있지 않는다면 어디든 둘 수 있다. 예를들어, 지시 사항이 1이라면 발의 위치는 다음 중 하나가 될 수 있다. { (1,0), (1,2), (1,3), (1,4) }

그러면 이제 dp를 어떻게 짜야할 지 어렴풋이 감이 올 것이다. 이 이전 상태에서의 각각 최솟값을 알고 있을 때, 다음 상태로의 최솟값을 찾으면 되는 것이다. 그러면 이 최솟값은 어떻게 찾아야 할까?

이전 상태에서 다음 상태로 간다는 것은 발 하나를 옮겨( 혹은, 유지하여) 지시 사항에 맞는 발의 위치를 가진다는 것이다. 그러면 이전 지시사항의 발을 이번 지시사항으로 옮기거나, 이전 지시사항의 발이 아닌것을 이번 지시사항으로 옮기는 경우만 생각하면 된다.

예를 들어 이전 지시사항이 1이었고 이번 지시사항이 2일 때, 1에 있는 발을 2로 옮기거나, 1에 있지 않은 발을 2로 옮기는 경우만 있다.

dp를 dp[지시사항][지시사항 아닌 쪽 위치] 로 만들어 진행하였다.

아래의 코드가 핵심이라 볼 수 있다.

 

for n, now_instruction in enumerate(instruction_list[1:-1], 1):
    ## prev_instruction 발을 now_instruction으로 옮기기
    for ii in range(5):
        dp[n][ii] = min(dp[n][ii],dp[n-1][ii] + change_cost(prev_instruction, now_instruction))

    ## prev_instruction이 아닌 발을 now_instruction으로 옮기기
    for ii in range(5):
        dp[n][prev_instruction] = min(dp[n][prev_instruction], dp[n-1][ii] + change_cost(ii, now_instruction))

전체코드

 

from sys import maxsize

def get_input():
    return list(map(int, input().split()))

def change_cost(A,B):
    offset = abs(A -B)
    ## 0에서 움직이는 경우
    if A == 0:
        return 2
    ## 안 움직이는 경우
    elif offset == 0:
        return 1
    ## 반대편으로 가는 경우
    elif offset == 2:
        return 4
    ## 옆으로 움직이는 경우
    else:
        return 3

# 지시사항이 주어졌을 때 가질수 있는 state는 3개
        # ex)   지시사항 = 1
        #       가질 수 있는 state = {(1,0), (1, 2), (1, 3), (1, 4)}
        # 이걸로 dp짜면 되겠다.
if __name__ == "__main__":
    # 입력 받기
    instruction_list = get_input()
    N = len(instruction_list) - 1
    dp = [[maxsize] * 5 for _ in range(N)]

    if not N: ## 지시사항이 없는 경우
        print(0)
    else:
        ## 첫번째 거 처리
        prev_instruction = instruction_list[0]
        dp[0][0] = 2
        #print(prev_instruction, dp[0])
        for n, now_instruction in enumerate(instruction_list[1:-1], 1):
            ## prev_instruction 발을 now_instruction으로 옮기기
            for ii in range(5):
                dp[n][ii] = min(dp[n][ii],dp[n-1][ii] + change_cost(prev_instruction, now_instruction))

            ## prev_instruction이 아닌 발을 now_instruction으로 옮기기
            for ii in range(5):
                dp[n][prev_instruction] = min(dp[n][prev_instruction], dp[n-1][ii] + change_cost(ii, now_instruction))
            #print(now_instruction, dp[n])
            prev_instruction = now_instruction
        print(min(dp[N-1]))

처음으로 백준 풀이 적은거라서 이해가 잘 안될 수 있을거 같다...