#9465 스티커

# 문제

# 입력 및 출력

# 풀이

처음에 풀었을 땐 접근 자체는 나쁘지 않았다고 보는데 코드가 엉터리였다

선택을 하지 않았을때를 따로 빼서 max 값을 구하도록 했는데 모든 케이스를 조회하지 못해 틀렸다

 

내 힘으로 풀고 싶어서 며칠 뒤에 다시 풀었다

 

i-1번째 열에서 선택한 행과 i번째 열에서 선택한 행을 쌍을 지어 생각하다 보니 해결할 수 있었다

 

i번째 열에서 첫 번째 행을 선택한 경우 i-1번째 열에서 선택하지 않은 경우와 두 번째 행을 선택한 경우의 max값을 구하고

이것을 계속 반복하면 된다

 

그리고 dp[n]은 모든 케이스의 max 값을 모아둔 경우기 때문에 여기서 max값을 구하면 최종 결과값이 된다

 

#include <iostream>
#include <algorithm>
using namespace std;
int dp[100001][3];
int arr[3][100001];

int main() {
	int T, n, res;
	cin >> T;
	while (T--) {
		cin >> n;
		for (int i = 1; i <= 2; i++) {
			for (int j = 1; j <= n; j++) {
				cin >> arr[i][j];
			}
		}
		for (int i = 1; i <= n; i++) {
			dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + 0;
			dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + arr[1][i];
			dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + arr[2][i];
		}
		res = max({ dp[n][0],dp[n][1],dp[n][2] });
		cout << res << "\n";
	}
}

dp는 점화식을 생각해내기가 힘들어서 그렇지 코드는 참 간단하다

 

뭔가 예전에 많이 풀어봤던 형식 같은데 조금만 꼬아서 내도 규칙을 알아차리기가 힘든 것 같다

그래도 구글링 없이 내 힘으로 풀었다는것에 의의를 둔다,,ㅎ