[ 백준 ] 20120번 - 호반우와 리듬게임 (C++)

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

20120번: 호반우와 리듬게임

 

 

[ 문제풀이 ]

 

1. dp[ N ]을 선언하고 dp[0] = 0, dp[1]은 첫 번째 수로 초기화 해줍니다. 이때, N은 콤보를 의미합니다.

 

2. i = 1 부터 i < N까지 수를 탐색하면서 j = i부터 j >= 1까지 콤보 값을 다음과 같은 점화식으로 갱신합니다.

tmp = max(tmp, dp[j]);
dp[j + 1] = dp[j] + 1LL * t * (j + 1);

dp[0] = max(n[1], n[2]);
dp[1] = dp[0] + t;
n[2] = n[1];
n[1] = tmp;

 

3. n[ 1 ], n[ 2 ], dp[ 1 ] ~ dp[ N ] 까지의 값 중 가장 큰 값을 ans에 저장합니다.

 

4. ans가 0보다 작다면 0을 아니라면 ans를 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#define ll long long
 
using namespace std;
 
int N;
ll dp[1001];
ll n[3];
ll ans;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
    cin >> dp[1];
    n[2] = n[1] = 0;
 
    for (int i = 1; i < N; i++) {
        int t;
        cin >> t;
        ll tmp = -5005000001;
        for (int j = i; j >= 1; j--) {
            tmp = max(tmp, dp[j]);
            dp[j + 1] = dp[j] + 1LL * t * (j + 1);
        }
        dp[0] = max(n[1], n[2]);
        dp[1] = dp[0] + t;
        n[2] = n[1];
        n[1] = tmp;
    }
    
    ans = max(n[1], n[2]);
 
    for (int i = 1; i <= N; i++) {
        ans = max(ans, dp[i]);
    }
 
    if (ans < 0) cout << 0;
    else cout << ans;
}