[백준 - 9465] 스티커

#include <iostream>
#include <algorithm>

#define MAX 100001
using namespace std;

int dp[MAX][3];
int arr[2][MAX];

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

	int T; cin >> T;

	while (T--)
	{
		//1. Get input value
		int N; cin >> N;
		for (int i = 0; i < 2; ++i)
		{
			for (int j = 1; j <= N; ++j)
			{
				cin >> arr[i][j];
			}
		}
		
		//2. Set initial value
		dp[1][0] = arr[0][1];
		dp[1][1] = arr[1][1];
		dp[1][2] = 0;

		//3. Do fill DP table
		for (int i = 2; i <= N; ++i)
		{
			dp[i][0] = max(dp[i - 1][2], dp[i - 1][1]) + arr[0][i];
			dp[i][1] = max(dp[i - 1][2], dp[i - 1][0]) + arr[1][i];
			dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]);
		}

		//4. Print
		cout << max(dp[N][0], max(dp[N][1], dp[N][2])) << "\n";
	}
	return 0;
}

---

||사고 과정

생각하는데 한 40분정도 소모했던 문제였다.

처음에 뭔가 직감적으로 일차원 테이브로는  풀지못하여 이차원 테이블인것 같았지만

인덱스마다 의미하는 것을 찾는게 어려웠다.

 

DP[ i ] [ j ] 에서 i는 분명 데이터의 개수를 뜻하는 것이니 j의 의미를 찾고 있던 와중에

데이터에서 나올 수 있는 경우의 수를 좀 더 집중적으로 생각했다.

상하좌우로 인접한 스티커는 땔수 없으니

하나의 열(i)에서 위의 스티커를 떼는 경우, 아래의 스티커를 떼는 경우, 떼지 않는 경우를 생각했다.

 

이 떼지 않는 경우를 생각하기가 어려웠는데 처음 본다고 생각하면

많은 스티커를 떼는게 목표지만 떼지 않는 경우를 구한다 라는게 와닿지 않았던것 때문이였던것 같다.

 

아무튼 이렇게 세가지를 j에 대응시켜서 손코딩으로 값을 찾아가니 점화식도 나오고 풀게 되었던 문제다.

---

||사용 기법

• DP

---

||풀면서 느낀 것

• 이차원 배열 테이블의 느낌

DP[i][j]라면 i는 데이터의 개수이고, j는 데이터에서 나올 수 있는 경우의수 를 뜻하는게 많았던것 같다.

• 넓게 생각하자

처음에는 무조건 많이 떼는게 최대가 나온다고 생각했지만 아니였다.

테스트 케이스가 아니였다면 생각하지 못했을거다.

어떻게 보면 예외처리를 잘하자라는 말ㅋㅋㅠ

• 테이블의 의미를 찾는게 이번에는 도움이 되었다.

경험상 의미를 찾으면 점화식도 금방 나오는것 같기에

다음에는 좀 더 집중해서 찾아봐야겠다.