백준 Silver 1 스티커

스티커 (백준 Silver 1)

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

항상 느끼는 거지만 DP는 너무 어려운 듯하다
거의 매 번 점화식을 세우는 법 찾아야 해서
늘 창의적인 풀이를 요구하는 듯 하다

DP(Dynamic Programming)

복잡한 문제를 하위 문제로 쪼개며 푸는 방식 중 하나이며
각각의 하위 문제의 결과를 저장하여 재사용 하는 방식

여러 최적화 문제에 사용되나
반복되는 값을 ‘재활용’할 수 있는 경우가 Dp이다
(재활용 안되면 분할정복에 가까워진다)

점화식(전이식)

‘이전 상태’들로부터 ‘현재의 상태’를 만드는 식

ex)

dp[i] = max(dp[i-1], dp[i-2] + arr[i]);

초기값(기저조건) : 반복,재귀의 시작점이 되는 기본 상태
(보통 dp[0] 등으로 표현)

보통 dp 배열의 개념은
특정 지점(n)까지 진행하였을 때
dp[n] 은 n까지 해당 문제에 해당하는 최적값

메모이제이션 (Top - Down)

재귀 + 기록을 통한 방식
dp[n] -> dp[n-1] -> dp[n-2] 처럼
위쪽에서 아래로 내려가는 방식이며
n이 점점 내려가고
하위 값들은 구한 뒤 재사용 되기에
메모 된다는 표현을 한다

• 구현이 직관적이며, 점화식 없이도 빠르게 시작 가능
  (물론 암묵적으로 점화식이 깔려있음)
  
• 다만 재귀 호출이기에 오버헤드나 오버플로우의 위험 존재
  

특정 상태에서 ‘다음 상태’로 어떻게 진행하면 될지
암묵적으로 판단이 가능하기에
구현이 조금 더 빠른 편

타뷸레이션 (Bottom - Up)

반복문을 통해 작은 상태부터 차례대로 채워나간다
보통 기저 상태를 먼저 설정한 후,
for 을 이용하여 주어진 목표 n 까지의 점화식으로 푼다
(반드시 명시적인 공식이 필요하다)

• 재귀 사용 x이기에 오버헤드 등이 없음
  
• 점화식을 ‘반드시’ 세워야 하기에 구현 난이도 있을 수 있음
  

성능상으로 Bottom-up 더 유리하기에
Top-Down으로 점화식을 찾은 후
Bottom-Up으로 최적화 하는 방식도 존재한다

이전에 정리한 글

내 포스팅

결과

DP 문제인 것이 판단되면 점화식을
세워보려는 노력이 필요하다

제출 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
	int t;
	cin >> t;
	while (t > 0)
	{
		int n;
		cin >> n;
		
		vector<long long> r1(n), r2(n);
		for (int i = 0; i < n; i++)
		{
			cin >> r1[i];
		}

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

		vector<vector<int>> dp(3,vector<int>(n+1));
		
		// 기저상태 설정
		dp[0][0] = r1[0]; // 위
		dp[1][0] = r2[0]; // 아래
		dp[2][0] = 0;     // 선택을 안하는 경우

		// 타뷸레이션
		for (int i = 1; i < n; i++)
		{
			dp[0][i] = r1[i] + max(dp[1][i-1], dp[2][i-1]);
			dp[1][i] = r2[i] + max(dp[0][i-1], dp[2][i-1]);
			int v = max(dp[0][i - 1], dp[1][i - 1]);
			dp[2][i] = max(v, dp[2][i]);
		}

		cout <<max( max(dp[0][n - 1], dp[1][n - 1]), dp[2][n - 1]) << '\n';

		t--;
	}

	return 0;
}