백준 9465번 스티커

🔒[문제 url]

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

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
using namespace std;

int t, n;
int cost[2][100'001];

int dp[2][100'001];

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> t;
}

void SOLVE()
{
	while (t--)
	{
		// Input
		cin >> n;
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < n; j++)
				cin >> cost[i][j];;

		// 초기 설정
		dp[0][0] = cost[0][0];
		dp[1][0] = cost[1][0];
		dp[0][1] = cost[0][1] + cost[1][0];
		dp[1][1] = cost[0][0] + cost[1][1];
		
		// Bottom Up Dynamic Programming
		/*
		* 첫번째 열(dp[?][0])부터 dp값을 설정해간다.
		* 예제 입력의 경우와같이, 한 개의 열을 건너뛰어야 최대값을 알 수는 있으나,
		* 두 개의 열을 건너뛰는 경우는 존재할 수 없음을 알 수 있다.
		*		--> 반드시 두 개의 열에 존재하는 값중 최소 한 값을 넣을 수 있음.
		* 따라서 i번째 열까지의 최댓값은,
		* 1) 첫번째 줄 i번째 열의 경우 :
		*		현재 위치의 값(cost[0][i])에 dp[1][i - 1]과 dp[1][i - 2]중
		*		최대값을 더한 것임을 알 수 있다.
		*		--> dp[0][i - 1]의경우 변을 공유해서,
		*			dp[0][i - 2]의경우 cost[1][i - 1]값을 건너뛰어서 불가능
		* 
		* 2) 두번째 줄 i번째 열의 경우 : 같은 이유로,
		* 		현재 위치의 값(cost[1][i])에 dp[0][i - 1]과 dp[0][i - 2]중
		*		최대값을 더한 것임을 알 수 있다.
		* 
		*/
		for (int i = 2; i < n; i++)
		{
			dp[1][i] = cost[1][i] + max(dp[0][i - 1], dp[0][i - 2]);
			dp[0][i] = cost[0][i] + max(dp[1][i - 1], dp[1][i - 2]);
		}

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

int main()
{
	INPUT();

	SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.