백준 2342번 - Dance Dance Revolution

https://www.acmicpc.net/problem/2342

2342번: Dance Dance Revolution

 

• 필요한 배경지식

다이나믹 프로그래밍

 

 

 

 

• 문제 해결 방법

3차원 배열을 사용하여 DP로 문제를 해결했습니다.

[1,4] 범위의 수가 N만큼 주워질때 배열 dp[n][x][y] = k에 대한 의미는 다음과 같습니다.

 

n의 범위: [0,N]

x, y의 범위: [0,4]

k: n번째 수까지 입력 받았을때, 두 발의 위치가 x, y인 경우에 사용된 최소의 힘

 

위와 같이 정의한다면 입력받은 i번째 수가 n인경우 다음과 같이 점화식을 세울 수 있습니다.

 

i-1번째 수에서의 왼발과 오른발의 위치가 각각 x,y일때

오른발이 y에서 n으로 이동한 경우 : dp[i][x][n] = min(dp[i][x][n], dp[i-1][x][y] + 필요한 힘);
왼발이 x에서 n으로 이동한 경우 : dp[i][n][y] = min(dp[i][n][y], dp[i-1][x][y] + 필요한 힘);

 

위치 a에서 b로갈때 필요한 힘의 계산은 calDist함수에 구현되어 있습니다.

 

 

 

 

• C++ 전체 코드

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

int n, i;
int dp[100001][5][5]{};

int calDist(int a, int b){ // a -> b
​​​​if(a==b) return 1;
​​​​if(a==0) return 2;
​​​​a--, b--;
​​​​if((a+1)%4==b || (a+3)%4==b) return 3;
​​​​else if((a+2)%4 == b) return 4;
​​​​else return INF;
}

int main() {
​​​​ios_base::sync_with_stdio(0);
​​​​cin.tie(0);
​​​​
​​​​memset(dp, 0x3f, sizeof(dp));
​​​​dp[0][0][0] = 0;

​​​​for(i=1; ; i++){
​​​​​​​​cin>>n;
​​​​​​​​if(n==0) break;
​​​​​​​​for(int x=0; x<5; x++) {
​​​​​​​​​​​​for(int y=0; y<5; y++){
​​​​​​​​​​​​​​​​if(dp[i-1][x][y]>=INF) continue;
​​​​​​​​​​​​​​​​int a = calDist(x,n);
​​​​​​​​​​​​​​​​int b = calDist(y,n);
​​​​​​​​​​​​​​​​dp[i][x][n] = min(dp[i][x][n], dp[i-1][x][y] + b); // y -> n
​​​​​​​​​​​​​​​​dp[i][n][y] = min(dp[i][n][y], dp[i-1][x][y] + a); // x -> n
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}

​​​​i--;
​​​​int ans = INF;
​​​​for(int x=0; x<5; x++){
​​​​​​​​for(int y=0; y<5; y++){
​​​​​​​​​​​​ans = min(ans, dp[i][x][y]);
​​​​​​​​}
​​​​}
​​​​cout<<ans;
}