[백준][9465번] 스티커

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

9465번: 스티커

 

 

풀이과정

 

1. dp문제이다

 

2. 스티커를 선택 할 수 있는 방법은 3가지이다

 

2N 스티커에서 한 열에 스티커를 선택 하는 방법은 아래와 같다.

X    O    X

X    X    O

dp[N][3] 배열을 만들었다.

 

X,X = 0, O,X = 1, X,O = 2 상태로 구분하여 풀었다.

 

N번째 스티커를 XX로 마무리 한다면 , max(dp[N-1][0] ~ dp[N-1][2]) 값이 이 된다.

N번째 스티커를 OX로 마무리 한다면,  max(dp[N-1][0] , dp[N-1][2]) + map[0][i] 값이 이 된다.

N번째 스티커를 XO로 마무리 한다면,  max(dp[N-1][0] , dp[N-1][1]) + map[1][i] 값이 이 된다. 

 

*map은 스티커의 점수이다.

 

이제 max(dp[N][0] ~ dp[N][2]) 값을 리턴하면 된다.

 

소스코드

#include <stdio.h>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
ull dp[100001][3];
int map[2][100001];

//state 0 X,X
//state 1 0,X
//state 2 X,0
ull solution(int n)
{
	for (int i = 1; i < n; i++) {
		dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][2]));
		dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + map[0][i];
		dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + map[1][i];
 	}
	return max(dp[n - 1][0], max(dp[n - 1][1], dp[n - 1][2]));
}

int main()
{
	int t, n;
	scanf("%d", &t);
	for (int tc = 0; tc < t; tc++) {
		scanf("%d", &n);
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < n; j++) {
				scanf("%d", &map[i][j]);
			}
		}
		dp[0][0] = 0;
		dp[0][1] = map[0][0];
		dp[0][2] = map[1][0];
		printf("%llu\n", solution(n));
	}
}