[백준] 9465: 스티커

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

9465번: 스티커

이전에는 실버 단계도 어려워서 못 풀었던 문제였는데 이제는 쉽게 느껴지는 문제였다.

대신 메모리를 잘 할당해야한다는 주의를 얻었다. 2 by n이면 충분했으나 까먹고 습관적으로 n by n 배열을 할당해 최초 시도 시에는 메모리 초과가 떴기 때문이다. 그래서 메모리 할당을 제대로 다시 해주니 정상적으로 통과가 된다.

 

하지만 이는 부수적인 거고, 핵심은 아니다.

핵심은 어떻게 스티커의 점수를 최대화할 것인지를 결정해야 한다.

 

문제를 읽다보면 스티커의 점수를 합하는 데에 일종의 패턴이 있다.

열을 우선하여 스티커를 방문하여 점수를 계산하다 보면 이전 열에서의 최대 스티커의 점수를 활용한다.

이러한 아이디어에 착안하여 최대 점수로부터 최대 점수가 나온다는 생각으로 해당 문제를 subproblem으로 잘게 쪼개, optimal한 값을 얻을 수 있다. 그렇다면 해당 스티커에서의 점수를 얻는 방법은 무엇이 있을까?

 

크게 2가지 방법이 있다.

 

1. 이전 열의 대각선 방향 행의 누적 점수에 해당 스티커의 점수의 합

2. 이전 열의 동일 방향의 행의 누적 점수(1번에서 해당 스티커를 합치는 것보다 그냥 포함을 안 하는 것이 유리)

 

예를 들어 $[i, j]$에서의 스티커를 택하는 경우 총 점수 $total_score(i, j)$를 계산하면,

 

$total_score(i, j) = max(score(1 - i, j - 1) + score(i, j), score(i, j  - 1) (j = 0 or 1)$

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<vector<int>> stickers(2, vector<int>(n));
        vector<vector<int>> dp(2, vector<int>(n));
        for(int i = 0;i < 2;i++) {
            for(int j = 0;j < n;j++) {
                cin >> stickers[i][j];
            }
        }
        
        dp[0][0] = stickers[0][0];
        dp[1][0] = stickers[1][0];
        
        for(int i = 1;i < n;i++) {
            for(int j = 0;j < 2;j++) {
                dp[j][i] = max(dp[j][i - 1], dp[1 - j][i - 1] + stickers[j][i]);
            }
        }
        
        cout << max(dp[0][n - 1], dp[1][n - 1]) << '\n';
    }
}