[파이썬] 백준 2342 : Dance Dance Revolution (골드3)

[파이썬] 백준 2342 : Dance Dance Revolution (골드3)

 

---

문제

---

풀이

0. 방향성 생각

발 옮기기 전 위치 -> 옮긴 후 위치 비용을 정리하는 딕셔너리 cost 정의

25개 상태 왼발5가지*오른발5가지, 각 상태로 올 수 있는 경우 중 가장 작은 코스트 선택

 

입력으로 1 2 2 4 0이 들어오면 마지막 0은 제외하고

stage 0에서 4개의 단계를 거쳐 stage 4에 도달해야한다.

각 stage에 도달하는 모든 상태를 확인하면서 DP 업데이트.

 

1. 입력, DP 초기화

import sys
input = lambda : sys.stdin.readline().rstrip()

command = list(map(int,input().split()))
stages = len(command)

dp = [[[1e6]*5 for _ in range(5)] for _ in range(stages)]
dp[0][0][0] = 0
cost = {(0,1):2,(0,2):2,(0,3):2,(0,4):2,
        (1,1):1,(1,2):3,(1,3):4,(1,4):3,
        (2,1):3,(2,2):1,(2,3):3,(2,4):4,
        (3,1):4,(3,2):3,(3,3):1,(3,4):3,
        (4,1):3,(4,2):4,(4,3):3,(4,4):1}

2. DP 업데이트

for stage in range(stages-1):
    cmd = command[stage]
    for left in range(5):
        for right in range(5):
            if dp[stage][left][right] != 1e6:
                state_now = dp[stage][left][right]
                state_l,cost_l = dp[stage+1][cmd][right],cost[(left,cmd)]
                state_r,cost_r = dp[stage+1][left][cmd],cost[(right,cmd)]
                
                if state_now + cost_l < state_l:
                    dp[stage+1][cmd][right] = state_now + cost_l
                if state_now + cost_r < state_r:
                    dp[stage+1][left][cmd] = state_now + cost_r

현재 상태가 1e6인 경우는 있을 수 없는 경우이다. 이 경우 다음 상태로 변하지 않으므로 제외.

1e6이 아닌 경우에는 발을 움직이면서 비용을 dp[stage][left][right]만큼 쓴 상태이다.

이 때 다음 상태로 가는 경우 중 왼발을 옮기는 경우 중 다음 stage DP값보다 작은 경우 업데이트한다.

기본적으로 1e6이 저장돼있다. 이 때 처음 도달하면 바로 업데이트, 그 이후에 도달하면 더 작은 값이면 업데이트한다.

오른발도 마찬가지로 업데이트한다.

3. 출력

answer = 1e6
for row in dp[-1]:
    for val in row:
        if val < answer: answer = val
print(answer)

마지막 stage에 도달해서 끝난 상태일 때 배열 한 번 순회하고 가장 작은 값 출력.

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

command = list(map(int,input().split()))
stages = len(command)

dp = [[[1e6]*5 for _ in range(5)] for _ in range(stages)]
dp[0][0][0] = 0
cost = {(0,1):2,(0,2):2,(0,3):2,(0,4):2,
        (1,1):1,(1,2):3,(1,3):4,(1,4):3,
        (2,1):3,(2,2):1,(2,3):3,(2,4):4,
        (3,1):4,(3,2):3,(3,3):1,(3,4):3,
        (4,1):3,(4,2):4,(4,3):3,(4,4):1}

for stage in range(stages-1):
    cmd = command[stage]
    for left in range(5):
        for right in range(5):
            if dp[stage][left][right] != 1e6:
                state_now = dp[stage][left][right]
                state_l,cost_l = dp[stage+1][cmd][right],cost[(left,cmd)]
                state_r,cost_r = dp[stage+1][left][cmd],cost[(right,cmd)]
                
                if state_now + cost_l < state_l:
                    dp[stage+1][cmd][right] = state_now + cost_l
                if state_now + cost_r < state_r:
                    dp[stage+1][left][cmd] = state_now + cost_r
answer = 1e6
for row in dp[-1]:
    for val in row:
        if val < answer: answer = val
print(answer)