[PS 백준 - 5.2] 9465번: 스티커

문제 정보

백준 9465번 - 바로가기

• 난이도: 실버 2
• 알고리즘: 다이나믹 프로그래밍

---

코멘트

이 문제도 DP 블로그의 코드를 그대로 가져와서 풀었다.

• [Parameters]
  • col: 스티커 열
  • status: 0이면 왼쪽에 아무 스티커 포함x, 1이면 왼쪽 상단 스티커 포함, 2이면 왼쪽 하단 스티커 포함
• [base case]
  • 스티커 열이 마지막에 도달
• [Logic]
  result의 디폴트 값은 status가 0일때이고, status가 1이 아니면 상단 칸의 스티커를 포함시키고 다음 단계를 확인한다. 또 2가 아니면 하단 칸의 스티커를 포함시키고 다음 단계를 확인한다. 이렇게 나온 값들 중에서 가장 큰 값을 골라 메모이제이션 + 리턴한다.

---

소스 코드

<탑다운 방식>

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

int score[2][100001];
int dp[100001][3];
int n;

int sticker(int col, int status) {

	if (col == n) return 0; // base case
	if (dp[col][status] != -1) return dp[col][status]; // memoization

	int result = sticker(col + 1, 0);
	if (status != 1) {
		result = max(result, score[0][col] + sticker(col + 1, 1));
	}
	if (status != 2) {
		result = max(result, score[1][col] + sticker(col + 1, 2));
	}
	dp[col][status] = result;
	return result;
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		for (int a = 0; a < 2; a++) {
			for (int j = 0; j < n; j++) {
				int tp;
				cin >> tp;
				score[a][j] = tp;
			}
		}
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < 3; k++) {
				dp[j][k] = -1;
			}
		}
		cout << sticker(0, 0) << "\n";
	}
	
}

---

<바텀업 방식> - by zzoni

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

int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    for (int t = 0; t < T; t++) {
        int N; cin >> N;
        int dp[2][100001]; // 최대값들의 합 배열
        int sc[2][100001]; // 점수 저장 배열
        for (int j = 0; j < 2; j++) {
            for (int k = 1; k <= N; k++)
                cin >> sc[j][k];
        }
        dp[0][0] = dp[1][0] = 0;
        dp[0][1] = sc[0][1]; dp[1][1] = sc[1][1];
        for (int i = 2; i <= N; i++) {
            dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + sc[0][i];
            dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + sc[1][i];
        }
        cout << max(dp[0][N], dp[1][N])<<"\n";
    }

    return 0;
}