백준 2342(Dance Dance Revolution) c++

문제

2342번: Dance Dance Revolution

(왼발, 오른발) 이 처음에 (0, 0)으로 시작해 수열이 주어지면 왼발과 오른발 둘중 아무나 그 위치로 움직여 춤을 추는 점수를 최소로

만드는 프로그램을 만드는 것입니다.

점수는 처음에 (0, 0)에서 아무 곳이나 2점을 얻습니다. 그 다음 발이 인접한 곳으로 이동할 때는 3점을 얻고 정반대인 곳으로 이동하면

4점을 얻습니다. 예를 들어 1에서 2나 4로 갈 떄는 3점을 얻지만, 3으로 갈때는 4점을 얻게 됩니다.

 

이 문제는 dp로 풀 수 있었다.

먼저 점화식을 세워야 하는데 dp[n][l][r] = (l, r) 위치일 때 n번째 발판부터 밟았을 때 최소점수 입니다.

발은 왼발을 움직이는 경우와 오른발을 움직이는 경우 총 2가지가 존재합니다.

따라서 다음과 같은 점화식이 세워집니다.

dp[n][l][r] = min(dp[n+1][n번째 발판][r]+왼발의 위치 점수, dp[n+1][l][n번째 발판]+오른발 위치점수)

---

int score[5][5];
for(int i=0;i<=4;i++)score[i][i]=1;
for(int i=0;i<=4;i++)score[0][i]=2;
score[1][2]=score[1][4]=score[2][1]=score[2][3]=score[3][2]=score[3][4]=score[4][3]=score[4][1]=3;
score[1][3]=score[2][4]=score[3][1]=score[4][2]=4;

먼저 score 배열을 만들어 줍니다. score[from][to] = from에서 to까지 가는 점수입니다.

vector<int>v;
while(1){
    int a;
    cin>>a;
    if(a==0)break;
    v.push_back(a);
}

입력 부분입니다. 발판을 밟는 순서입니다.

int sol(int n, int l, int r){
    if(n==v.size())return 0;
    int &ret = dp[n][l][r];
    if(ret!=0)return ret; //메모이제이션
    return ret = min(sol(n+1, v[n], r)+score[l][v[n]],sol(n+1, l, v[n])+score[r][v[n]]);
}

점화식을 바탕으로 재귀적으로 메모이제이션을 사용하며 해결하였습니다.

---

전체 코드입니다.

#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>

#define INF 2000000000
using namespace std;
using ll = long long;
vector<int>v;
int dp[100001][5][5];
int score[5][5];
int sol(int n, int l, int r);
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    while(1){
        int a;
        cin>>a;
        if(a==0)break;
        v.push_back(a);
    }
    for(int i=0;i<=4;i++)score[i][i]=1;
    for(int i=0;i<=4;i++)score[0][i]=2;
    score[1][2]=score[1][4]=score[2][1]=score[2][3]=score[3][2]=score[3][4]=score[4][3]=score[4][1]=3;
    score[1][3]=score[2][4]=score[3][1]=score[4][2]=4;
    cout<<sol(0, 0, 0);

	return 0;
}
int sol(int n, int l, int r){
    if(n==v.size())return 0;
    int &ret = dp[n][l][r];
    if(ret!=0)return ret; //메모이제이션
    return ret = min(sol(n+1, v[n], r)+score[l][v[n]],sol(n+1, l, v[n])+score[r][v[n]]);
}