oVeron

https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net dp[k][i][j] : k번째 지시사항에서 왼발은 i, 오른발은 j에 위치해 있다. 점화식을 구해보자. k+1번째 지시로 이동할 곳이 x라 할 때 dp[k][i][j] = min( dp[k+1][x][j], dp[k+1][i][x] )이다. 즉 왼발이 x로 이동할 때, 오른발이 x로 이동할 때로 나누어서, 이동할 때의 비용을 반영해 그 최솟값을 구하면 된다. #..

알고리즘/baekjoon 2023. 1. 30. 10:48