[2342] Dance Dance Revolution

2023-04-19 | Algorithms / 백준 문제 풀이 모음 # Python, Gold 3

백준 문제 풀이

문제 링크

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)