C언어 백준 9465번 스티커

문제 풀이

이번 DP 문제는 각 셀의 값, 스티커 누적 점수를 배열에 담아 누적하는 구조로 문제를 풀이할 수 있다.

 

기본 구조

현재 스티커 점수인 배열 arr을 선언하고, 스티커 누적 점수인 배열 dp를 선언하여 사용한다.

위와 같이 arr과 dp 기본 구조를 만들 수 있다.

 

스티커 선택 (점화식 세우기)

이제 어떤 방식으로 스티커를 선택해야 최대 누적 값을 얻을 수 있을까? 바로 'N'번 째 선택을 할 때 N-1번 째 스티커와의 관계를 생각하면 된다.

 

맨 오른쪽인 N번 째로 생각 해 보면, 아래 1번과 2번 패턴 밖에 없다.

스티커 누적 점수는 이전 스티커 최댓값에 현재 선택하는 스티커 최댓값을 더하는 구조이다.

따라서 선택 셀[1]은 고려할 필요는 없고, 선택 셀[2]의 누적 점수에 선택 셀[3]을 더 하면 된다.

1번 패턴

선택 셀[1]		선택 셀[3]
	선택 셀[2]

2번 패턴

		선택 셀[5]
선택 셀[4]

정리하면, 아래 둘 중에 어떤 값이 더 큰지 비교하면서 선택 해 가면 최대 누적값이 나오게 된다.

		선택 셀[8]
선택 셀[6]	선택 셀[7]

소스

#include <stdio.h>
#include <string.h>
#define MAX(a,b) (((a)>(b))? (a):(b))


int main(void)
{
	int T;
	int n;

	int result;
	
	scanf("%d", &T);
	for (int i=0; i<T; i++)
	{
		result = 0;
		n=0;
		scanf("%d", &n);
		int arr[2][100100]={0,};
		int dp[2][100100]={0,};
		for (int j=0; j<2; j++)
		{
			for (int k=1; k<n+1; k++)
			{
				scanf("%d",&arr[j][k]);
			}
		}
		dp[0][0]=arr[0][0]=0;
		dp[1][0]=arr[1][0]=0;
		
		dp[0][1]=arr[0][1];
		dp[1][1]=arr[1][1];
		
		for (int l=2; l<n+1; l++)
		{
			{
				dp[0][l]=MAX(dp[1][l-2]+arr[0][l],dp[1][l-1]+arr[0][l]);
				dp[1][l]=MAX(dp[0][l-2]+arr[1][l],dp[0][l-1]+arr[1][l]);

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