[백준OJ] 9465번 스티커

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

9465번: 스티커

---

 

-풀이-

dp를 이용하여, 왼쪽에서 오른쪽으로 이동하며 최댓값을 갱신시키면 된다.

이때 3가지의 경우가 있다.

 

1) i번열의 스티커에서 0번째 줄의 스티커를 고른경우

2) i번열의 스티커에서 1번째 줄의 스티커를 고른경우

3) i번열의 스티커에서 아무것도 고르지 않은 경우

 

이 세가지 경우에 대해서 최댓값을 저장해주는 dp[3][100000]을 선언해준다. dp[i][j] 는 j열에서 위의 i번 경우의 최댓값이다.  ex) dp[1][8]= 8번째 줄에서 1번째줄의 스티커를 고른경우의 최댓값

 

그런뒤

1번의 경우) i열의 스티커에서 0번째 행의 스티커를 고를 수 있는 경우는, i-1번째 열에서 1번 스티커를 고르거나, i-1번째 열에서 아무것도 안골랐을때 i번째 열에서 0번째 행의 스티커를 고를 수 있다.

 

2번의 경우) i열의 스티커에서 1번째 행의 스티커를 고를 수 있는 경우는, i-1번째 열에서 0번 스티커를 고르거나, i-1번째 열에서 아무것도 안골랐을때 i번째 열에서 1번째 행의 스티커를 고를 수 있다.

 

3번의 경우) i열의 스티커에서 스티커를 아무것도 고르지 않는다면, 이전 열에서 0번째스티커를 골랐을때와 1번째 스티커를 골랐을때중 최댓값이 그대로 오면된다.

 

 

이를 이용해서 N-1번째 스티커까지 간 뒤, dp[0][n-1] , dp[1][n-1] , do[2][n-1] 중 최댓값을 출력해주면 된다.

 

-시간복잡도-

dp를 이용하여 문제를 풀기때문에 O(N)이 된다.

 

-코드-

 

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

int t, n;

int arr[2][100000] = { 0 };
int dp[3][100000] = { 0 };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> t;
	while (t--) {
		cin >> n;

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

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