백준 9465번 스티커 C++

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

다이나믹 프로그래밍 bottom-up 방식으로 풀 수 있는 문제이다.

우선 두 가지 경우가 있다.

 

1. 왼쪽 위에서 시작하는 경우

 

 

 

 

 

2. 왼쪽 아래에서 시작하는 경우

 

 

 

 

 

1번의 경우를 예를 들어 살펴보면

한 칸 떨어진 대각선을 선택하는 경우와 두 칸 떨어진 대각선을 선택하는 경우로 나눌 수 있다.

다른 어떤 곳을 선택하더라도 결국 이 두 가지로 나뉜다.

(100을 선택: 50->50->100, 20을 선택: 50->50->20 or 50->70->20, 10을 선택: 50->50->100->10)

위 경우들을 살펴보면 결국 위의 두 가지의 경우들의 조합으로 만든 선택임을 알 수 있다.

 

마지막 스티커까지 도달했을 때 1번의 경우와 2번의 경우 중 큰 값이 답이 된다.

 max(dp[0][n], dp[1][n])

 

소스코드

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>

using namespace std;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

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