[C/C++ 백준 9465번] 스티커 (Silver 2)

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

9465번: 스티커

되게 까다로웠던 문제. 

dp는 2차원 배열로 만든다. dp[i][j]는 i행 j열의 스티커가 살아있을 경우 해당 패턴에서 최대 점수 합이다.

그러니까 예를 들어 dp[1][5]인 경우는,

ㅇ	ㅇ	ㅇ	ㅇ	x
ㅇ	ㅇ	ㅇ	ㅇ	ㅇ

이 패턴에서의 최대 점수이다.

 

점화식을 만들기 위해 각 패턴에서 최대 점수가 나올수 있는 케이스가 무엇이 있는지 알아봐야한다. 일단 저 오른쪽 o를 떼는 경우,

ㅇ	ㅇ	ㅇ	ㅇ	x
ㅇ	ㅇ	ㅇ	x	(여기 점수 더하기)

그리고 저 o를 안떼었을 경우, 이 경우는 1, 4에 있는 스티커를 떼는 경우이다. (이 경우가 아니라면 나머지 모든 경우에서o를 뗄 수 있다.)

o	o	o	x	x
o	o	x	(여기 점수 더하기)	x

이 두가지의 경우가 가능하다. 두 경우 중 더 큰것을 저장하면 된다. 반대쪽은 같으니 생략.

---

#include <cstdio>
#include <algorithm>
using namespace std;
int main(void){
	int T, n, sticker[2][100001]={}, dp[2][100001], ans;
	dp[0][0]=0;
	dp[1][0]=0;
	//dp[i][j] : i행 j열에 있는 스티커가 남아있을때 최대 개수 
	scanf("%d",&T);
	for(int i=0; i<T; i++){//T개의 case 
		scanf("%d",&n);//열의 길이 
		for(int k=0; k<2; k++){
			for(int j=1; j<=n; j++){
				scanf("%d",&sticker[k][j]);
			}
		}
		for(int j=1; j<=n; j++){
			for(int k=0; k<2; k++){
				if(k==0)
					dp[k][j]=max(dp[1][j-1]+sticker[k][j],dp[1][j-2]+sticker[k][j-1]); 
				else
					dp[k][j]=max(dp[0][j-1]+sticker[k][j],dp[0][j-2]+sticker[k][j-1]); 
			}	
		}
	ans=max(dp[0][n], dp[1][n]);
	printf("%d\n",ans);
	}
}

---