[백준 C++] 9465번: 스티커

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

 

사자 우리에 넣는것과 비슷한 문제라 생각하고 풀이했다.

 

3차원 dp 배열 dp[100001][3]을 선언하고 앞에는 n의 수를 넣어주고 뒤에는 0일때는 안채웠을때 최대값, 1일때는 위에칸 채웠을때 최대값, 2일때는 아래칸 채웠을때 최대값을 넣어주었다.

 

그리고 최대값을 비교할때 식을 이런식으로 세웠다.

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

 

또한 초항은 

dp[0][0] = 0;
dp[0][1] = score[0][0];
dp[0][2] = score[0][1];

 

요런식으로 먼저 넣어주었다.

 

전체코드이다.

#include <iostream>
#include <algorithm>
#define MAX 100001
using namespace std;
int dp[MAX][3] = { 0, };
int score[MAX][2] = { 0, };
 
int main(int argc, char* argv[])
{
	int test_case;
	cin >> test_case;
 
	for (int T = 1;T <= test_case;T++) {
		int n;
		cin >> n;
 
		for (int i = 0;i < n;i++) {
			cin >> score[i][0];
		}
		for (int i = 0;i < n;i++) {
			cin >> score[i][1];
		}
 
		dp[0][0] = 0;
		dp[0][1] = score[0][0];
		dp[0][2] = score[0][1];
 
		for (int i = 1;i < n;i++) {
			dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]);
			dp[i][1] = max((dp[i - 1][0] + score[i][0]), (dp[i - 1][2] + score[i][0]));
			dp[i][2] = max((dp[i - 1][0] + score[i][1]), (dp[i - 1][1] + score[i][1]));
		}
 
		dp[n][0] = max(max(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
 
		cout << dp[n][0] << '\n';
 
	}
 
	return 0;
}

 

처음에 좀 해멨지만 금방 바로 잡고 풀 수 있었던 문제, 

 

dp의 공식 찾아내는 방법은 문제를 작게 나누어 푸는 법, 이전으로 돌아가지 않고 푸는 법 이라며 설명을한다.

 

하지만 나는 "컴퓨터 기억메모리를 쓰는 대신 연산을 어떻게 하면 더 적게할까?" 이런식으로 먼저 생각하는것 같다.