[알고리즘][DP] 9465번 스티커 | baekjoon 문제 풀이

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

9465번: 스티커

 

 

풀이

 

일단 최대한 최소의 경우로 나누어 생각해보았다.

 

- 열 단위로 선택.

- 경우의 수: 둘다 선택 X / 1행만 선택 / 2행만 선택.

 

점화식을 작성하려니까 감이 오지 않아서, 다른 블로그를 참고하게 되었다.

 

---

 

<경우의 수>

 

아래의 그림처럼

sticker[0][0]을 선택하는 경우와

sticker[1][0]을 선택하는 경우로 나누어 볼 수 있다.

 

<문제의 점화식>

 

아래와 같이 생각할 수 있고,

아래의 그림과 같이 0번째 열의 값을 모두 0으로 두어 계산하면 된다.

 

sticker[0][i] = max(sticker[1][i - 2], sticker[1][i - 1]) + sticker[0][i]
sticker[1][i] = max(sticker[0][i - 2], sticker[0][i - 1]) + sticker[1][i]

 

 

<코드>

#include <iostream>
using namespace std;

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

	int n, T;
	cin >> T;

	for (int i = 0; i < T; i++) {
		cin >> n;
		int sticker[2][100001];
		sticker[0][0] = 0;
		sticker[1][0] = 0;

		for (int j = 0; j < 2; j++) {
			for (int k = 1; k <= n; k++) {
				cin >> sticker[j][k];
			}
		}

		for (int j = 2; j <= n; j++) {
			sticker[0][j] = max(sticker[1][j - 2], sticker[1][j - 1]) + sticker[0][j];
			sticker[1][j] = max(sticker[0][j - 2], sticker[0][j - 1]) + sticker[1][j];
		}
		cout << max(sticker[0][n], sticker[1][n]) << '\n';
	}
}