[DP (동적 프로그래밍) / BOJ 2342 / C++] Dance Dance Revolution

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

2342번: Dance Dance Revolution

이 문제도 이전에 풀었던 DP와 같은 유형!!

 

값을 거꾸로 타고 올라가면서 계속해서 값을 갱신해나가면 된다!

 

계속해서 dp 배열에 넣는 논리는 똑같은데, dp에 저장할 상태값은 현위치, 왼발위치, 오른발위치로 정의해줄 수 있다.

 

그리고 추가적으로 가해지는 힘이 달라지는 부분 구현은 최대한 간단한 것부터 구현해나가면 편하다.

po 함수를 유심히보자!

 

#include <bits/stdc++.h>
#define INF 500000;

using namespace std;

int arr[100001], N;
int dp[100001][5][5]; // 현위치 / 왼발, 오른발

int po(int from, int to){ // from 에서 to로.
    if(from==to) return 1; // 같은지점 한번 더 누를 시 1.
    else if(from==0) {return 2;} // 시작지점 0이면 힘은 2.
    else if(abs(from-to)==2) {return 4;} // 서로 반대방향이면 3<->1, 2<->4
    else {return 3;} // 그밖에 모든 경우는 3
}

int go(int level, pair<int, int> now){
    if(level==N) return 0;
    
    int &mid = dp[level][now.first][now.second];
    
    if(mid) return mid;
    
    mid = min(go(level+1, {arr[level], now.second}) + po(now.first, arr[level]),
              go(level+1, {now.first, arr[level]}) + po(now.second, arr[level])); // 왼발 , 오른발
    
    return mid;
    
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    
    for(int i = 0 ;; i++){
        cin >> arr[i];
        if(arr[i]==0) {N=i; break;}
    }
    
    
    
    cout << go(0, {0,0}) << '\n';
    
}