백준 9465 스티커

백준 9465 스티커

www.acmicpc.net/problem/9465

9465번: 스티커

스티커 문제의 경우 대각선으로 이동하는 경우 어떻게 많은 값을 가지고 이동할 수 있는가가 문제이다. 이전 퇴사 문제의 경우에도 선택하지 않을 경우가 있어서 스티커와 비슷한 문제라고 착각했다. 

 

우선 조건부터가 많이 다르다. 퇴사문제의 경우 N이 1000개, 스티커의 경우 100000이다. 즉 일부분을 직접 방문해보면서 문제를 해결하기에는 시간초과가 발생한다는 의미이다. 그래서 dp의 이전 값의 정보를 활요하여 문제를 해결해야한다. 

 

140 + 60, 200 + 60중 큰  것을 선택하여 값이 들어갔다. 

 

140 + 60, 200 + 60중 큰  것을 선택하여 마지막 값이 들어갔다. 

 

현재 위치에서 앞으로 한칸 혹은 두칸 이동할 수 있다. dp는 이때 각 위치의 정보를 이전 값, 이전 전값의 크기를 비교해서 각각의 최대의 값을 구성하도록 정보를 저장한다. 따라서 아래와 같은 점화식이 만들어질 수 있다. 

dp[i][1] = max(dp[i-1][0], dp[i-2][0]) + map[i][1];
dp[i][0] = max(dp[i-1][1], dp[i-2][1]) + map[i][0];

 

다음에는 문제를 잘보며 하나 이전인지 둘 이전인지 잘 체크하면서 문제를 풀어야겠다. 굳이 전체를 다 방문할 필요는 없다. 

#include <cstdio>
#include <algorithm>
#include <string.h>

using namespace std;

int map[100002][3];
int dp[100002][3];

void solve();
void dpSolve();

int main(){
	int T;
	scanf("%d", &T);

	for(int i = 0; i < T; i++)
		solve();
}

int N;
void solve(){
	memset(map, 0, sizeof(map));
	memset(dp, 0, sizeof(dp));

	scanf("%d", &N);

	for(int j = 0; j < 2; j++)
		for(int i = 1; i <= N; i++)
			scanf("%d", &map[i][j]);
	
	dp[1][0] = map[1][0];	
	dp[1][1] = map[1][1];

	dpSolve();

	printf("%d\n", max(dp[N][0], dp[N][1]));
}

void dpSolve(){
	for(int i = 2; i <= N; i++){
		dp[i][1] = max(dp[i-1][0], dp[i-2][0]) + map[i][1];
		dp[i][0] = max(dp[i-1][1], dp[i-2][1]) + map[i][0];
	}
}