백준 9465: 스티커/C++

📌문제접근

문제 : 백준 9465: 스티커

• 2*n 행렬의 스티커가 있고, 스티커는 0~100사이 정수값을 가짐
• 한 스티커를 선택하면 해당 스티커와 인접한 좌우상하의 스티커는 사용할 수 없음
• 최대 점수가 되는 스티커 조합의 점수를 결과로 출력
• 1 <= n <= 100,000

접근 방법

• n이 10만까지의 값을 가지므로 n^2의 시간복잡도는 불가 -> 이중 for문이 있으면 안되겠다.
• 스티커의 모든 점수는 양수이기에 스티커를 선택할 수 있다면 선택하는게 무조건 좋다.
• 2*n 이라고 할때 2 *(n-1)의 결과값을 이용할 수 있을까?
  - [0][n]을 선택하는 경우, [0][n-1] 스티커는 사용 불가, [1][n-1] 스티커 사용 가능
  - 또는 [*][n-1] 스티커는 선택하지 않고, [1][n-2] 스티커 사용 가능
  - 두 값을 비교하여 최대값을 선택하면 됨.

📌제출코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
	int T;
	
	cin >> T;
	
	for (int t=0; t<T; t++){
		int n;
		cin >> n;
		
		int arr[2][100001] = {0,};
		int dp[2][100001] = {0, };
		int result = 0;
		
		for (int i = 1; i <= n; i++){
			cin >> arr[0][i];
		}
		for (int i = 1; i <= n; i++){
			cin >> arr[1][i];
		}
		
		if (n == 1){
			result = max(arr[0][1], arr[1][1]);
			cout << result << '\n';
			continue;
		}
		if (n == 2){
			result = max(arr[0][1]+arr[1][2], arr[1][1]+arr[0][2]);
			cout << result << '\n';
			continue;
		}
		
		dp[0][1] = arr[0][1];
		dp[1][1] = arr[1][1];
		dp[0][2] = arr[0][2] + arr[1][1];
		dp[1][2] = arr[1][2] + arr[0][1];
	
		
		if (n >= 3){
			for (int i = 3; i <= n; i++){
				dp[0][i] = arr[0][i] + max(dp[1][i-1], dp[1][i-2]);
				dp[1][i] = arr[1][i] + max(dp[0][i-1], dp[0][i-2]);
			}
			result = max(dp[0][n], dp[1][n]);
			cout << result << '\n';
		}
	}
	return 0;
}