[2020 Goricon] BOJ 20120 호반우와 리듬게임

문제 링크 : www.acmicpc.net/problem/20120

20120번: 호반우와 리듬게임

DP문제의 대표유형인 계단오르기 문제와 유사한 문제이다.

각 노트를 처리하는 것과 계단을 한 번 오르는 것을 동일하게 생각한다면 수월하게 문제를 해결할 수 있다.

단 점수를 계산하기 위해선 현재까지 몇 콤보로 현재 노트를 처리하는지에 대한 정보가 필요하므로, 이 풀이에서는 dp 배열을 2차원으로 두었다.

k번 노트를 c 콤보에서 처리한 경우, 다음과 같은 선택지가 존재한다.

① k + 1번 노트를 처리할 경우 : 연속된 노트를 처리했으므로, 콤보를 유지한 채 점수를 갱신한다.

따라서 dp[k + 1][c + 1] = max(dp[k + 1][c + 1], dp[k][c] + score[k + 1] * (c + 1))

② k + 2 또는 k + 3번 노트를 처리할 경우 : 노트를 건너뛰었으므로, 콤보가 초기화된다.

따라서 dp[k + 2][1] = max(dp[k + 2][1], dp[k][c] + score[k + 2]) (k + 3도 동일)

 

연속된 노트 3개를 건너뛰면 점수가 0으로 고정되므로, 이는 마지막에 한 번만 비교해주면 된다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
 
#define INF 999999999999
 
using namespace std;
typedef pair<int, int> p;
typedef long long ll;
 
int n;
vector<int> notes;
//노트 번호, 콤보 횟수
ll dp[1001][1001];
 
void init() {
    int input;
    cin >> n;
    notes.push_back(0);
    for (int i = 0; i < n; i++) {
        cin >> input;
        notes.push_back(input);
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = -INF;
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    ll answer = 0;
 
    init();
 
    dp[1][1] = notes[1];
    dp[1][0] = 0;
 
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            //노트를 틀리지 않았을 때
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + notes[i + 1] * (j + 1));
 
            //노트 하나를 건너뜀
            if (i + 2 > n) {
                dp[n][0] = max(dp[n][0], dp[i][j]);
                continue;
            }
            dp[i + 2][1] = max(dp[i + 2][1], dp[i][j] + notes[i + 2]);
 
            //노트 둘을 건너뜀
            if (i + 3 > n) {
                dp[n][0] = max(dp[n][0], dp[i][j]);
                continue;
            }
            if (i == 1 && j == 0) continue;
            dp[i + 3][1] = max(dp[i + 3][1], dp[i][j] + notes[i + 3]);
        }
    }
 
    for (int i = 0; i <= n; i++) {
        answer = max(answer, dp[n][i]);
    }
 
    printf("%lld\n", answer);
 
    return 0;
}