백준 BOJ 9465 - 스티커

3연DP.

www.acmicpc.net/problem/9465

9465번: 스티커

이경우에는 1차원으로 비벼보려했는데

걍 2차원하는게 편할거같다

dp[2][123456]으로 만들어주고

dp[i][j]는 (i,j)에 있는 스티커를 땔때의 최대값이 된다.

여기서 조심해야할 점은

단순히 W나 M같은 꼴로만 탐색한다는 것이 아닌데, 이는 문제의 예시케이스에서도 볼 수 있듯이

체스의 나이트같은 위치에서도 최댓값을 가질 수 있다. 이것만 신경써주면 무난하게 AC.

 

+ 세그폴트가 안나오게 하기 위해서는 dp[k][1]을 따로 미리 처리해주어야하고,

   dp배열은 매번 테스트케이스가 나올때마다 초기화를 해주어야한다.

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

int dp[2][123456] = {0};
int a[123456] = {0};
int b[123456] = {0};

int main(){
	int t;
	int n;
	scanf("%d", &t);
	while(t--){
		memset(dp,0,sizeof(dp));
		scanf("%d", &n);
		for(int i=1; i<=n; i++) scanf("%d", &a[i]);
		for(int i=1; i<=n; i++) scanf("%d", &b[i]);
		
		dp[0][1] = a[1];
		dp[1][1] = b[1];
		for(int i=2; i<=n; i++){
			dp[0][i] = max(dp[1][i-1], dp[1][i-2]) + a[i];
			dp[1][i] = max(dp[0][i-1], dp[0][i-2]) + b[i];
		}
		printf("%d\n", max(dp[0][n], dp[1][n]));
	}
	return 0;
}

배열초기화에 간단하게 memset함수를 썼다.