[2342] Dance Dance Revolution

2342번: Dance Dance Revolution

DDR? 게임에서 발을 어떻게 이동시키는 것이 힘이 덜 드는지 계산하는 방식이다. 처음에는 그리디(?)하게 움직이나 생각을 했는데 발을 움직일때 마다 최소가 되도록 선택하면 총합에서 더 크게 나오는 경우가 있었다. 즉 이 문제는 그리디가 아니라, 오른발 왼발을 각각 움직인 상태들 모두 기록해두고 최소값을 찾아야 한다.

예를 들면, 현재 발위치가 0,0 이다. 처음에 1번을 눌러라 라는 지시에 왼발을 쓸지, 오른발을 쓸지 경우의 수가 나뉘게 된다. 그러면 현재 발 위치에서 왼발을 변경하면 (1, 0)이 되고, 오른발을 움직이면 (0, 1) 이 된다. 다음 지시에서는 2를 눌러라 라는 지시가 있다면.. 또 총 경우의 수가 4개가 된다. 처음에는 이점을 간과하고 그냥 모든 경우의 수를 다 저장했더니…

메모리 초과가 나왔다… 지시가 많으면 많을 수록 스텝을 밟는 경우의 수가 많은데, 굳이 모두 저장하지 않고, 지시마다 나올 수 있는 경우의 수를 저장하고 경우의 수 중 중복된 것들은 최솟값으로 저장되도록 하였다.

지시를 따를때마다 경우의 수가 2배가 되는데, 이러면 경우의 수가 너무 많아 메모리 초과가 나는 것이다. 그래서 나는 발의 위치를 해시(딕셔너리)로 최솟값(현재 스텝의 최솟값)을 넣도록 처리했다. 이러면 무수한 경우의 수 중 유의미한 값만 처리 할 수 있다.

하나씩 설명하면 다음과 같다.

우선 저장해야하는 값이, 왼발, 오른발 위치, 이제까지 든 힘으로 3가지를 각각 경우의 수마다 저장해야한다. 위에서 이야기한데로 해시로 처리하는데 각 경우의 수는 왼발, 오른발로 결정되기 때문에 왼발 오른발을 튜플로 두고, 해당 값을 해시의 키값으로 지정한다.

steps = {(0, 0): 0}

현재 발의 위치를 steps 라는 해시에 담는다. 처음에는 둘다 (0, 0)에 있기 때문에 초기값을 설정한다. 각각 지시(nums로 두었다.)에 따라서 왼발, 오른발을 움직인다. 다음 함수를 통해서 현재 발의 위치와 다음 발의 위치를 비교해서 드는 힘을 반환한다.

def move_step(step, next_step, power):
    move = abs(int(next_step - step))
    npower = power
    if step == 0:
        npower += 2
    else:
        if move == 0:
            npower += 1
        elif move == 2:
            npower += 4
        else:
            npower += 3
    return npower

움직일 때 힘을 계산하는 함수가 있으니, 현재 발 위치(steps)의 키값을 가져온다.

for step in steps:
    left, right = step 
    power = steps[step]
    npower = move_step(left, next_step, power)
    if npower < nstep.get((next_step, right), sys.maxsize):
        nstep[(next_step, right)] = npower

    npower = move_step(right, next_step, power)
    if npower < nstep.get((left, next_step), sys.maxsize):
        nstep[(left, next_step)] = npower
steps = nstep

위 코드 처럼 각각 왼발, 오른발 드는 힘을 저장하고, move_step이라는 함수로 왼발, 오른발일때 값을 찾는다. 이러면 현재 지시에 따른 경우의 수가 nstep에 저장한다. nsteps에는 n번째 지시에 따른 모든 경우의 수가 저장되어서 n+1 지시에서는 현재 발의 위치로 전환된다.

즉, 경우의 수를 구하고 현재 발의 위치를 해당 경우의 수로 전환하면, 마지막 에는 이 경우의 수 중 가장 작은 값을 출력하면 된다.

    min = sys.maxsize
    for j in steps:
        if min > steps[j]:
            min = steps[j]

    print(min)

풀이

import sys

def move_step(step, next_step, power):
    move = abs(int(next_step - step))
    npower = power
    if step == 0:
        npower += 2
    else:
        if move == 0:
            npower += 1
        elif move == 2:
            npower += 4
        else:
            npower += 3
    return npower

if __name__ == "__main__":
    nums = list(map(int, sys.stdin.readline().split()))

    steps = {(0, 0): 0}
    count = len(nums) - 1
    for i in range(count):
        nstep = {}
        next_step = nums[i]
        for step in steps:
            left, right = step
            power = steps[step]
            npower = move_step(left, next_step, power)
            if npower < nstep.get((next_step, right), sys.maxsize):
                nstep[(next_step, right)] = npower

            npower = move_step(right, next_step, power)
            if npower < nstep.get((left, next_step), sys.maxsize):
                nstep[(left, next_step)] = npower
        steps = nstep
        
    min = sys.maxsize
    for j in steps:
        if min > steps[j]:
            min = steps[j]

    print(min)