[백준] 9465번 스티커

9465번: 스티커

문제에 나와있는 예제로

스티커가 2행 1열까지라고 생각할 때 두 가지 경우로 나눌 수 있다.

 

1. [0][0]을 선택하는 경우

[0][0]=50

Sticker	[0]
[0]	50
[1]	30

 

2. [1][0]을 선택하는 경우

[1][0]=30

Sticker	[0]
[0]	50
[1]	30

 

여기서 1은 [0][0]에 저장하고

2는 [1][0]에 저장한다.

 

 

스티커가 2행 2열이라고 생각할 때도 이렇게 두 가지 경우가 나온다.

 

1. [0][1]을 선택하는 경우

[1][0]+[0][1]=40

Sticker	[0]	[1]
[0]	50	10
[1]	30	50

 

2. [1][1]을 선택하는 경우

[0][0]+[1][1]=100

Sticker	[0]	[1]
[0]	50	10
[1]	30	50

 

여기서 1은 [0][1]에 저장하고

2는 [1][1]에 저장한다.

 

 

스티커가 2행 3열일 때부터는 각 경우에서 두 가지 경우로 또 나뉜다.

 

1-1. [0][2]를 선택하는 경우

[1][1]+[0][2]=200

Sticker	[0]	[1]	[2]
[0]	50	40	100
[1]	30	100	70

 

1-2. [0][2]를 선택하는 경우

[1][0]+[0][2]=130

Sticker	[0]	[1]	[2]
[0]	50	40	100
[1]	30	100	70

 

이때 1-1에서는 [0][0]은 선택할 필요가 없다.

왜냐하면 이미 [1][1]은 [1][1]까지 왔을 때의 최댓값이 저장되어 있기 때문이다.

 

즉, 현재 스티커를 선택했을 때 선택할 수 있는 직전의 스티커만 생각해주면 되므로

1-1 : 전 대각선에 있는 [1][1]도 선택하는 경우

1-2 : 전 전 대각선에 있는 [1][0]도 선택하는 경우

이 두가지 경우만 생각해주면 된다.

 

2-1. [1][2]를 선택하는 경우

[0][1]+[1][2]=110

Sticker	[0]	[1]	[2]
[0]	50	40	100
[1]	30	100	70

 

 2-2. [1][2]를 선택하는 경우

[0][0]+[1][2]=120

Sticker	[0]	[1]	[2]
[0]	50	40	100
[1]	30	100	70

 

최댓값을 구하는 문제이므로

1-1, 1-2 이 두 가지 경우 중에서 더 큰 값인 1-1을 [0][2]에 저장하고

2-1, 2-2 이 두가지 경우 중에서 더 큰 값인 2-2를 [1][2]에 저장해야 한다.

 

 

이런 식으로 끝까지 표를 채우고 나면 [0][N-1], [1][N-1] 중 더 큰 값을 출력해주면 된다.

 

Sticker	[0]	[1]	[2]	[3]	[4]
[0]	50	40	200	140	250
[1]	30	100	120	210	260

 

이 예제에서는 [1][4]인 260이 답이 된다.

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int T, N;
	cin >> T;
	for (int t = 0; t < T; t++) {
		cin >> N;
		int sticker[2][100001] = { 0 };
		for (int i = 0; i < 2; i++) for (int j = 0; j < N; j++) cin >> sticker[i][j];

		if (N > 1) sticker[0][1] += sticker[1][0], sticker[1][1] += sticker[0][0];
		for (int i = 2; i < N; i++) {
			sticker[0][i] += max(sticker[1][i - 1], sticker[1][i - 2]);
			sticker[1][i] += max(sticker[0][i - 1], sticker[0][i - 2]);
		}
		cout << max(sticker[0][N - 1], sticker[1][N - 1]) << "\n";
	}
	return 0;
}