[백준OJ] 9465번 스티커

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

9465번: 스티커

---

 

풀이

dp[i][j]=k 라고 할때, i번째열에서 j번째 스티커를 골랐을떄 ( 0 = 첫번째 스티커 / 1 = 두번째 스티커 / 2 = 아무것도 선택 x ) 0번째~i번째 열까지의 스티커점수의 최댓값을 k라고 하자.

 

먼저

1. i번열에서 첫번째 스티커를 고르기 위해서는 i-1번 열에서 두번째 스티커를 고른경우와 i-1번 열에서 아무것도 고르지 않은 경우가 있다. 이 두 경우중에서 더 큰쪽과 i번열의 첫번째 스티커를 더해주면, i번열에서 첫번째 스티커를 고른경우, i번열까지의 최댓값이 나온다.

 

2. i번열에서 두번째 스티커를 고르기 위해서는 i-1번 열에서 첫번째 스티커를 고른경우와 i-1번 열에서 아무것도 고르지 않은 경우가 있다.  이 두 경우중에서 더 큰쪽과 i번열의 두번째 스티커를 더해주면, i번열에서 두번째 스티커를 고른경우, i번열까지의 최댓값이 나온다.

 

3. i번열에서 아무 스티커도 고르지 않는다면, i-1번열에서 첫번째스티커를 고른경우, 두번째 스티커를 고른경우, 아무것도 고르지 않은경우중 가장 큰 경우를 가지고 오면된다.

 

시간복잡도

O(N)

 

반응형

코드

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

int maze[100001][2];
int dp[100001][3] = { 0 };
int t, n;

void input() {
	cin >> n;

	for (int j = 0; j < 2; j++) {
		for (int i = 0; i < n; i++) {
			cin >> maze[i][j];
		}
	}
}

int DP() {

	dp[0][0] = maze[0][0];
	dp[0][1] = maze[0][1];

	for (int i = 1; i < n; i++) {
		//1번째꺼 선택 = i-1에서 2번째꺼선택+1번째꺼 / i-1에서 아무것도 선택x+1번째꺼중 큰거
		dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + maze[i][0];

		//2번째꺼 선택 = i-1에서 1번째꺼선택+i번째에서 2번째꺼 / i-1에서 아무것도 선택x + 2번째꺼 중 큰거
		dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + maze[i][1];

		//아무것도 선택 x = i-1에서 가장 큰거
		dp[i][2] = max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][2]));
	}
	return max(dp[n - 1][0], max(dp[n - 1][1], dp[n - 1][2]));
}

void solve() {
	input();
	cout<< DP()<<"\n";
}

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

	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}