[C++] 백준 9465

---

문제 링크

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

풀이 전략

2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.
단순히 dp2차원 배열을 만들어서 각 대각선의 합을 구하면 될 것 같지만. 예시로 나온 

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

이 그림의 점수를 선택하는 것을 보았을 때, 100 다음 줄에 있는 10과 40을 선택한다 하더라도 60이 더 크기 때문에 60을 선택하는 모습을 볼 수 있다. 

만약 숫자가 
50, 10, 100
30, 50, 70
인 경우를 생각해보자. 
숫자를 선택하는 경우는 총 4가지이다. 
0번 인덱스를 골랐을 때, (여기서 0번 인덱스는 0행을 의미합니다.)
50, 10, 100            50, 10, 100 
30, 50, 70             30, 50, 70

1번 인덱스를 골랐을 때, (여기서 1번 인덱스는 1행을 의미합니다.)
50, 10, 100           50, 10, 100
30, 50, 70             30, 50, 70
따라서 이를 통해

dp[i][0] = arr[i][0] + std::max(dp[i - 1][1], dp[i - 2][1]);
dp[i][1] = arr[i][1] + std::max(dp[i - 1][0], dp[i - 2][0]);​

이러한 점화식을 구할 수 있다. dp는 지금까지의 거쳐온 숫자를 더한 배열이고, arr는 현재 스티커의 점수를 담은 array이다. 

여기에서 중요한 점은 
50, 10, 100             50, 10, 100
30, 50, 70              30, 50, 70
과 같은 경우는 고려하지 않는 것이다.
왜냐하면 위의 경우를 선택하는 것보다 중간에 있는, 50과 10을 고르는 것이 더 많은 합을 구할 수 있기 때문이다.

여기에서 문제에 나와있듯이 정답의 최댓값은 100 * 100000 =10,000,000이기 때문에 int형으로 선언해도 충분하다.  

코드 

#include <iostream>
#include <vector>

static inline void solution() {
	int n;

	std::cin >> n;
	std::vector<std::vector<int>> arr(n + 1, std::vector<int>(2));
	std::vector<std::vector<int>> dp(n + 1, std::vector<int>(2));

	for (int i = 0; i < 2; ++i) {
		for (int j = 1; j <= n; ++j) {
			std::cin >> arr[j][i];
		}
	}
	dp[0][0] = dp[0][1] = 0;
	arr[0][0] = arr[0][1] = 0;
	dp[1][0] = arr[1][0];
	dp[1][1] = arr[1][1];

	for (int i = 2; i <= n; ++i) {
		dp[i][0] = arr[i][0] + std::max(dp[i - 2][1], dp[i - 1][1]);
		dp[i][1] = arr[i][1] + std::max(dp[i - 2][0], dp[i - 1][0]);
	}

	std::cout << std::max(dp[n][0], dp[n][1]) << std::endl;
}

int main(void) {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	int t;

	std::cin >> t;
	while (t--)
		solution();
	return (0);
}

 

회고

첫번째 시도에 점화식을 이끌어 내는 것은 성공하였지만 이를 코드로 작성하는 것이 조금 어려웠다. 나는 dp에 마지막 더한 숫자의 인덱스를 넣을 생각을 했었는데, 이러니까 코드의 양도 많아지고 생각할 것도 많았다. 
dp를 이루는 큰 줄기가 2개 밖에 되지 않기 때문에 두가지 경우의 수를 모두 구하는 것이 더 좋은 방법인 것 같다. 

 

더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)