백준 9465번 _ 스티커

2020-05-09 · 배운 것 · 3분 읽기

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

9465번: 스티커

풀이방법

선택의 경우가 3가지가 있다.

위의 경우들을 끝까지 갈때까지 반복하면됨.

전체코드

#include <iostream>
#include <algorithm>
using namespace std;

int stikers[3][1000001];
int dp[3][1000001];
int n;

void dpInit()
{
	for (int i = 0; i <= 3; i++)
		for (int j = 0; j <= n; j++)
			dp[i][j] = -1;
}

void Input()
{
	cin >> n;
	for (int i = 1; i <= 2; i++)
		for (int j = 1; j <= n; j++)
			cin >> stikers[i][j];
}

int getMaxValue(int status, int here)
{
	int& ret = dp[status][here];
	if (ret != -1) return ret;
	ret = 0;

	if (status != 0 && here == n)
		return ret = stikers[status][here];

	if (status == 0 && here == n)
		return ret = max(stikers[1][here], stikers[2][here]);
	

	//선택 no
	ret = max(ret, getMaxValue(0, here + 1));
	//선택 1
	if(status == 1 || status == 0)
		ret = max(ret, getMaxValue(2, here + 1) + stikers[1][here]);
	//선택 2
	if(status == 2 || status == 0)
		ret = max(ret, getMaxValue(1, here + 1) + stikers[2][here]);

	return ret;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int testcase;
	cin >> testcase;
	for (int i = 0; i < testcase; i++)
	{
		Input();
		dpInit();
		cout << getMaxValue(0, 1) << '\n';
	}
	return 0;
}

후기

쉬운 dp도 나한텐 어렵네..