[백준] 20120번: 호반우와 리듬게임

경북대학교 고리콘 대회 문제 : www.acmicpc.net/contest/view/545

2020 경북대학교 Goricon

문제 주소 : www.acmicpc.net/problem/20120

20120번: 호반우와 리듬게임

문제 확인

 

dp문제

현재 노트를 치거나 버리는 경우로 나눌 수 있으며 다음과 같은 스텝으로 나눌 수 있습니다.

• 치는 경우 : dp[j + 1] = dp[j] + (j+1) * 수
• 버리는 경우 : k_1의 값 수정

계산 시 최대 버릴 수 있는 노트는 2개 까지이며 주의해야 할 점은 3개 이상의 노트를 버리고 0으로 만들 수 있습니다. 계산 결과가 음수인 경우 3개의 노트를 연속으로 버려 0으로 제출하여야 정답이 됩니다.

 

풀이

 

dp 풀이 시 전 단계의 모든기록은 필요 없으며 연속으로 한번, 두 번 놓쳤을 때 가질 수 있는 최댓값만을 저장하여 메모리 사용량, 배열 탐색의 시간 모두 절약할 수 있습니다.

노트를 치는 경우 dp[j + 1]에 기록 해 두며  j+1 -> 1 순으로 역순으로 기록하여 배열을 재사용할 수 있습니다.

k_1, k_2 변수를 이용하여 노트를 버리는 경우의 최댓값을 기록하고 이는 현재 단계 1~j 까지의 값 중 최댓값을 선택하여 기록합니다. 그 후 다음 노트를 입력받고 k_1, k_2 중 큰 값을 선택하여 dp[0]에 기록하고 위 과정을 진행합니다.

 

코드

#include <cstdio>
int main() {
    int n;
    long long dp[1001], k_1 = 0, k_2 = 0, tmp;
    scanf("%d\n%lld", &n, &dp[1]);
    dp[0] = 0;
    for (int t, i = 1; i < n; i++) {
        scanf("%d", &t);
        tmp = -9223372036854775807;
        for (int j = i; j >= 1; j--) { // j = 콤보
            tmp = dp[j] > tmp ? dp[j] : tmp; //최댓값 선택 -> 노트를 버리는 경우
            dp[j + 1] = dp[j] + (j + 1) * t; //dp 갱신
        }
        dp[0] = k_1 > k_2 ? k_1 : k_2; //콤보 0에 기록해둔 후 이를 계속해서 사용해감
        dp[1] = dp[0] + t;//k_1, k_2 상태에서 노트를 친 경우
        k_2 = k_1;//k_2 갱신
        k_1 = tmp;
    }
    tmp = k_1> k_2 ? k_1 : k_2;
    for (int i = 1; i <= n; i++)
        tmp = dp[i] > tmp ? dp[i] : tmp;
    printf("%lld", tmp > 0 ? tmp : 0);
}
/*
사용한 테스트 케이스
7
-1 3 4 -7 -2 -2 1
 
7
-100000 5 -100000 5 -100000 5 -100000
 
8
-1 -1 -1 -1 100 100 -10000 100
 
11
-1 -1 -1 -100000000 -1 -1 -1 -1 -1 -1 10000
 
*/