[C] 백준 - 9465번: 스티커

4월 15일(월) - 다이나믹 프로그래밍 (9465번)

9465번: 스티커

---

최초 생각 정리

---

문제점

---

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int sticker[2][100001];
int dp[2][100001];

int MAX(int x, int y)
{
	return ((x > y) ? (x) : (y));
}

int main(void)
{
	int T;
	scanf("%d", &T);

	int n;
	while (T--)
	{
		scanf("%d", &n);

		for (int i = 0; i <=1 ; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				scanf("%d", &sticker[i][j]);
			}
		}

		dp[0][0] = dp[1][0] = 0;
		dp[0][1] = sticker[0][1];
		dp[1][1] = sticker[1][1];

		for (int i = 2; i <= n; i++)
		{
			dp[0][i] = MAX(dp[1][i - 1], dp[1][i - 2]) + sticker[0][i];
			dp[1][i] = MAX(dp[0][i - 1], dp[0][i - 2]) + sticker[1][i];
		}

		int score = MAX(dp[0][n], dp[1][n]);
		printf("%d\n", score);
	}

	return 0;
}

---