[백준 9465번] 스티커 (C++)

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

9465번: 스티커

---

스티커 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 

 

테이블 d[i][j]는 d[0]부터 d[i]까지의 스티커를 선택했을 때, 스티커 점수의 최댓값으로 정의했습니다. (단, d[i][j] 스티커는 반드시 선택)

 

초기값은 아래와 같습니다.

// 단, board는 2행 n열의 스티커 배열을 의미함
d[0][0] = board[0][0]; d[1][0] = board[1][0];
d[0][1] = board[1][0] + board[0][1]; d[1][1] = board[0][0] + board[1][1];

50, 30, 40점인 스티커를 선택한 경우에만 100점인 스티커를 선택할 수 있습니다. 

50	10	100	20	40
30	40	70	10	60

또한, 50, 10, 30점인 스티커를 선택한 경우에만 70점인 스티커를 선택할 수 있습니다. 

50	10	100	20	40
30	40	70	10	60

현재 스티커를 선택할 수 있는 경로 중 점수가 가장 큰 것을 선택하면됩니다.

따라서 테이블 d[i][j]는 아래와 같이 정의할 수 있습니다.

d[0][i] = max({d[0][i - 2], d[1][i - 2], d[1][i - 1]}) + board[0][i];
d[1][i] = max({d[0][i - 2], d[1][i - 2], d[0][i - 1]}) + board[1][i];

 

결과는 d[0][n], d[1][n] 중 큰 값을 출력해주면 됩니다. 

 

아래는 Bottom-Up 방식의 다이나믹 프로그래밍 코드입니다. 

#include <bits/stdc++.h>
using namespace std;

int board[2][100010];
int d[2][100010];   // d[i][j]는 d[0]부터 d[i]까지의 스티커를 선택했을 때, 스티커 점수의 최댓값 (단, d[i][j] 스티커는 반드시 선택) 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t, n; cin >> t;
    while(t--){
        fill(&board[0][0], &board[1][100000], 0);   // 2행 N열의 스티커 초기화
        
        cin >> n;
        for(int i = 0; i < 2; i++)
            for(int j = 0; j < n; j++)
                cin >> board[i][j]; // 각 스티커의 점수 입력 받음
        
        // 초기값 지정
        d[0][0] = board[0][0]; d[1][0] = board[1][0];
        d[0][1] = board[1][0] + board[0][1]; d[1][1] = board[0][0] + board[1][1];
        
        // 테이블 채우기
        for(int i = 2; i < n; i++){
            d[0][i] = max({d[0][i - 2], d[1][i - 2], d[1][i - 1]}) + board[0][i];
            d[1][i] = max({d[0][i - 2], d[1][i - 2], d[0][i - 1]}) + board[1][i];
        }
        
        cout << max(d[0][n - 1], d[1][n - 1]) << "\n";  // 결과 출력
    }
}

 

아래는 문제 풀이에 사용된 테스트케이스입니다.

1
5
50 10 100 20 90
30 50 20 10 60
-> 300