문제
백준 - 2342번: Dance Dance Revolution
분석
눌러야 하는 숫자가 순서대로 주어질 때, 가장 힘을 적게 사용했을 때의 사용한 힘을 구하는 문제이다. (만약 어떤 번호를 연속으로 눌러야 한다면, 누른 발로 반복해서 눌러야 한다.)
입력된 수열의 길이는 최대 100,000이다. 따라서 백트래킹으로 모든 경우의 수를 구하는 것에는 무리가 있다. 그리디로 생각하면 항상 옳은 결과가 나오지 않는다.
따라서 dp 배열에 누르는 순서에 따라 진행하면서 두 발의 위치에 따른 현재까지 사용한 최소 힘을 기록하기로 했다.
각 버튼마다 발을 옮길 때 사용하는 힘은 power에 딕셔너리로 저장해둔다.
0에서 나머지 1,2,3,4로 옮기면 2
같은 곳을 한 번 더 누르면 1
둘의 차가 2면 4, 아니면 3
i는 눌러야 하는 숫자의 차례가 되며, order[i]가 0이면 마지막을 의미하므로 진행을 멈춘다.
left, right는 각각 왼쪽, 오른쪽 발이 위치한 숫자를 나타낸다. (0,1,2,3,4)
따라서 dp 배열의 크기는 (입력받은 수열크기) x 5 x 5가 된다.
dp[i][left][right] = '현재까지 사용한 최소 힘' 을 저장하는 것으로 나타낸다.
오른쪽 발을 옮길 때, 왼쪽 발이 이미 누르려는 숫자에 위치하지만 않으면 옮길 수 있다.
move(i+1, left, num)에 옮길 때 사용한 힘 power[(right, num)]을 더하면 된다.
마찬가지로 왼쪽 발은, 오른쪽 발이 이미 누르려는 숫자에 위치하지만 않으면 옮길 수 있다.
따라서 move(i+1, num, right)에 옮길 때 사용한 힘 power[(left, num)]을 더하면 된다.
그렇게 구한 값 중 작은 것이 dp[i][left][right]에 저장된다.
move(0, 0, 0)에서 시작하여 order[i]가 0이면 재귀를 멈추고 값을 반환한다.
코드
해결언어 : Python
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
order = list(map(int, input().split()))
power = {}
for i in range(1, 5):
power[(0, i)] = 2
for j in range(1, 5):
if i == j:
power[(i, j)] = 1
elif abs(i-j) == 2:
power[(i, j)] = 4
else:
power[(i, j)] = 3
dp = [[[0]*5 for _ in range(5)] for _ in range(len(order))]
def move(i, left, right):
if order[i] == 0:
return 0
if dp[i][left][right]:
return dp[i][left][right]
num = order[i]
mn = sys.maxsize
if left != num:
mn = min(mn, move(i+1, left, num)+power[(right, num)])
if right != num:
mn = min(mn, move(i+1, num, right)+power[(left, num)])
dp[i][left][right] = mn
return mn
print(move(0, 0, 0))
pypy는 재귀 깊이 106 때문에 메모리 제한에 걸린다.
3차원 배열 말고도 defaultdict(dict)를 사용하여 dp[i][(left, right)] 같은 형태로 사용할 수 있다.
끝으로..
프로그래머스 '숫자 타자 대회' 문제와 유사한 문제였다. 문제들을 많이 풀어볼 수록 유사한 문제들이 기억나는 경우가 많아지는 것 같다.
