[BOJ] 백준 2342 Dance Dance Revolution

문제 링크

www.acmicpc.net/problem/2342

2342번: Dance Dance Revolution

 

풀이

지시 사항의 인덱스, 왼발의 위치, 오른발의 위치를 가지고 dp를 돌려줍시다.

 

각각 왼발을 옮겼을 때, 오른발을 옮겼을 때로 전개하며, 현재 위치와 다음 위치의 차이에 따른 값만 바꿔주며 정답에 더해주면 됩니다.

 

정답 코드

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
 
int d[111'111][5][5];
int p[111'111];
int n;
 
int getVal(int now, int next){
    if(now == 0) return 2;
    if(now == next) return 1;
    return 3 + (now % 2 == next % 2);
}
int go(int i, int l, int r) {
    if (i == n) return 0;
    int &ret = d[i][l][r];
    if (ret != -1) return ret;
    ret = INF;
    int next = p[i];
    ret = min(ret, go(i + 1, next, r) + getVal(l, next));
    ret = min(ret, go(i + 1, l, next) + getVal(r, next));
    
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(d, -1, sizeof(d));
 
    for (int i = 0; cin >> p[i], p[i] != 0; i++, n++);
    cout << go(0, 0, 0);
}