[C언어/DP] 9465 : 스티커

 

 

#include<stdio.h>
#include<string.h>
#define MAX 100005
int max(int a,int b){
	return a>=b?a:b;
}
int main(void){
	int t,n;
	int dp[MAX][3],arr[MAX][2];
	scanf("%d",&t);
	
	for(int k=0;k<t;k++){
		memset(dp,0,sizeof(dp));
		memset(arr,0,sizeof(arr));
		
		scanf("%d",&n);
		for(int h=0;h<2;h++){
			for(int w=0;w<n;w++){
				scanf("%d",&arr[w][h]);
			}
		}
		
		dp[0][0]=arr[0][0];
		dp[0][1]=arr[0][1];
		dp[0][2]=0;
		for(int w=1;w<n;w++){
			for(int h=0;h<3;h++){
				dp[w][0]=max(dp[w-1][1]+arr[w][0],dp[w-1][2]+arr[w][0]);
				dp[w][1]=max(dp[w-1][0]+arr[w][1],dp[w-1][2]+arr[w][1]);
				dp[w][2]=max(dp[w-1][0],dp[w-1][1]);
			}
		}
		
		printf("%d\n",max(max(dp[n-1][0],dp[n-1][1]),dp[n-1][2]));
	}
}

 

위 코드 수정

#include<stdio.h>
#include<string.h>
#define MAX 100005
int max(int a,int b){
	return a>=b?a:b;
}
int main(void){
	int t,n;
	int dp[MAX][2],arr[MAX][2];
	scanf("%d",&t);
	
	for(int k=0;k<t;k++){
		memset(dp,0,sizeof(dp));
		memset(arr,0,sizeof(arr));
		
		scanf("%d",&n);
		for(int h=0;h<2;h++){
			for(int w=0;w<n;w++){
				scanf("%d",&arr[w][h]);
			}
		}
		
		dp[0][0]=arr[0][0];
		dp[0][1]=arr[0][1];
		for(int w=1;w<n;w++){
			for(int h=0;h<3;h++){
				dp[w][0]=max(dp[w-1][1]+arr[w][0],dp[w-1][0]);
				dp[w][1]=max(dp[w-1][0]+arr[w][1],dp[w-1][1]);
			}
		}
		
		printf("%d\n",max(dp[n-1][0],dp[n-1][1]));
	}
}