BOJ 9456 스티커

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

1. 문제요약

- 2xn 스티커 배열

- 한장을 떼면 변을 공유하는 좌, 우, 상 또는 하 의 스티커는 못쓰게 됨

- 스티커당 점수가 있는데 뗀 스티커의 점수의 최대 합은?

- 1 <= n <= 100,000

2. 접근방법

- 브루트 포스로 접근하면, 2^100000 

  못품

- dp로 접근하면,

  

  : 회색 스티커를 뗀다면, 노란색 스티커 또는 초록색 스티커를 뗀 경우 최대가 된다

  : 각각 회색이 윗칸을 뗀경우, 아랫칸을 뗀 경우로 구분

3. 시간복잡도

- n

4. 회고

소스코드

#include<iostream>
using namespace std;

int t, n, d[2][100002];

int max(int a, int b){
	return ((a < b) ? b : a);
}

int main(void){
	cin >> t;
	while (t--){
		cin >> n;
		int a, b;
		for (int i = 0; i < 2; i++)
			for (int j = 1; j <= n; j++)
				cin >> d[i][j];
		for (int i = 2; i <= n; i++){
			d[0][i] += max(d[1][i - 1], d[1][i - 2]);
			d[1][i] += max(d[0][i - 1], d[0][i - 2]);
		}
		cout << max(d[0][n], d[1][n]) << "\n";
	}
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]