[BOJ] 1462번 : 퀴즈쇼

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

1462번: 퀴즈쇼

 

아주 재미있는 DP 문제이다. 얼핏 보면 2006정올 도대회 초등부 4번 '계단 오르기'(https://www.acmicpc.net/problem/2579)와 비슷해 보이지만 다르다. 처음엔 비슷한 문제로 보고 접근했다가 틀렸다.

 

가장 다른 점은 현재 풀고 있는 문제 i와 현재 가지고 있는 코인 개수 j를 가지고 2차원 DP table을 짜면 time complexity와 space complexity 둘 다 문제의 조건에 충족되지 못한다는 점이다. 따라서 현재 가지고 있는 코인 개수 j를 계산에서 배제하는 방법에 대한 고민, 그 경우에 어떻게 O(1)만에 점수를 계산할 수 있을 것인가에 대한 고민이 필요하다.

 

가장 중요한 아이디어는 코인의 개수를 row, 현재 풀고 있는 문제 번호를 column으로 시각화해 보았을 때, 코인을 0개 가지고 있는 경우를 제외하고는 모두 이전의 왼쪽 위에서 점수를 더한 값으로 그 DP table에서 가질 수 있는 최대 점수가 계산된다는 점이다. 

 

남은 코인개수(row)/ 현재 풀고 있는 문제(column)	1번	2번	3번	4번	5번
0개	-150	130	200	160	500
1개	150	-130	160	240	210
2개	NaN	170	-100	200	290

이 경우 (0,x)를 제외한 모든 row의 항 (t,u)는 다음과 같이 간단하게 계산될 수 있다.

 

따라서 이 항들은 굳이 매번 계산할 필요가 없다. 우리가 찾는 것은 마지막 column의 최댓값이고, 각 column의 최댓값은 이전 column의 최댓값 또는 bonus를 얻은 경우의 점수 둘 중 하나에서만 얻어진다. 왜냐하면 각 column의 항들의 값은 이전 column의 값들에서 모두 같은 수인 score[i]를 더해준 것이므로, 대소 관계는 변하지 않기 때문이다.

 

하지만 0번째 row와 보너스를 얻었을 경우의 점수는 다르다. 0번째 row는 max(이전 column에서의 최댓값-score[i], bonus를 획득했을 경우 점수)로 결정된다. 따라서 bonus를 획득했을 경우의 점수를 O(1)로 구하면 된다. 이는 누적합 배열을 통해 간단하게 해결 가능하다. 따라서 0번째 row의 항들도 O(1) 안에 구할 수 있다.

 

이를 정리하여 쓰면 다음과 같다.

그 column에서의 보너스를 얻었을 경우의 점수는 (i-m번째 column의 코인이 0일 경우의 점수) + 점수 누적합 + 보너스 점수로 계산할 수 있다.

 

i번째 column에서 coin이 0개일 떄의 최댓값은, max(보너스를 얻은 경우의 점수, 이전 column에서의 최댓값에서 점수 차감분을 뺀 값)으로 구할 수 있다.

 

마지막으로 각 column에서의 최댓값은 max(보너스를 얻은 경우의 점수, 이전 column에서의 최댓값에서 점수를 더한 값)으로 구할 수 있다.

 

이렇게 구현할 경우 time complexity는 O(N)이다.

 

#include <iostream>
#include <algorithm>
#define NINF -98765432198
 
using namespace std;
 
typedef long long int ll;
const int maxN = 500500;
int n, m;
int score[maxN], bonus[maxN];
ll scoreAcc[maxN], zeroScore[maxN];
 
ll calcMaxScore() {
    ll bonusResult = 0;
    ll maxScore= 0;
    int maxIndex = 0;
    for(int i = 1; i<= n; i++) {
        if(i<m) bonusResult = NINF;
        else bonusResult = zeroScore[i-m]+scoreAcc[i]-scoreAcc[i-m]+bonus[i];
        zeroScore[i] = max(bonusResult, maxScore-score[i]);
        if(bonusResult>=maxScore+score[i]) {
            maxScore = bonusResult;
            maxIndex = 0;
        }
        else {
            maxScore += score[i];
            maxIndex++;
        }
    }
    return max(zeroScore[n],maxScore);
}
 
int main(void) {
 
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &score[i]);
        scoreAcc[i]=scoreAcc[i-1]+(ll)score[i];
    }
    for(int i = 1; i <= n; i++) scanf("%d", &bonus[i]);
    
    cout<<calcMaxScore()<<endl;
}

 

 

이 코드는 또한 내 github에서도 확인할 수 있다.

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/1462/1462.cpp

Jordano-Jackson/PS