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

#문제

www.acmicpc.net/problem/9465

9465번: 스티커

#풀이 & 학습한 내용

supremo7.tistory.com/100에서 풀었던 동물원 문제와 매우 유사한 문제이다. 한 열을 기준으로 위아래가 모두 비어있는 경우 index 0에, 위에만 있는 경우 index 1에, 아래에만 있는 경우 index 2에 각각의 optimization을 저장한다. 동물원에서는 경우의 수를 구했다면, 이 문제에서는 최대합을 구한다. 소스코드의 25~27행에 해당하는 optimal substructure를 구하고, basis로 첫 번째 열에 대한 정보를 넣어준 뒤에 for문을 통해 마지막 열까지 dp배열을 채운다. 그리고 dp[0][N-1], dp[1][N-1], dp[2][N-1] 중 최댓값을 답으로 출력해준다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
long long p[2][100002];
long long dp[3][100002];
 
int main(void) {
    int N;
    int T;
    cin >> T;
    while (T--) {
        cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> p[0][i];
        }
        for (int i = 0; i < N; i++) {
            cin >> p[1][i];
        }
 
        dp[0][0] = 0; dp[1][0] = p[0][0]; dp[2][0] = p[1][0];
 
        for (int i = 1; i < N; i++) {
            dp[0][i] = max({dp[0][i - 1], dp[1][i - 1], dp[2][i - 1]});
            dp[1][i] = max({dp[0][i - 1] ,dp[2][i - 1] }) + p[0][i];
            dp[2][i] = max({dp[0][i - 1] ,dp[1][i - 1] }) + p[1][i];
        }
        cout << max({ dp[0][N - 1], dp[1][N - 1], dp[2][N - 1] }) << '\n';
    }
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Dynamic_Programming/BOJ_9465.cpp

HoYoungChun/BOJ_algorithm