Posts [백준] 9465번 - 스티커
Post
Cancel

[백준] 9465번 - 스티커


백준 온라인 저지의 9465번 스티커 떼기 문제입니다.

[링크] https://www.acmicpc.net/problem/9465


문제 조건과 설명

  • 2행 n열로 배치된 스티커 표가 있습니다.
  • 여기서 스티커 한 칸을 떼면, 그 스티커와 변을 공유하는 스티커들은 모두 찢어져 사용할 수 없게 됩니다.
  • 즉, 뗀 스티커의 왼쪽,오른쪽,위,아래 스티커는 사용할 수 없게 됩니다.
  • 각 스티커에 점수를 매기고 스티커를 뗄 때, 뗄 수 있는 스티커들의 점수의 최댓값을 구해야 합니다.

  • [예시]

위와 같이 50, 50, 100, 60을 뗐을 경우, 점수의 합이 260으로 최대가 될 수 있습니다.


Input

첫째 줄에는 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스의 첫째 줄에는 n (1<=n<=100,000)이 주어집니다.

다음 두 줄에는 n개의 정수가 주어지며 이들은 그에 위치한 스티커의 점수에 해당합니다.


Output

각 테스트 케이스마다, 2n개의 스티커 중 뗄 수 있는 스티커들의 점수 최댓값을 출력합니다.


생각한 아이디어

처음에는 DP라고 하여 막연하게 규칙을 찾으려고 했습니다.

하지만 DP는 단순하게 규칙 찾는 것도 방법이 될 수는 있지만, 이전 값이 다음 값에 어떻게 영향을 미칠지를 자세히 생각해야 했습니다. 저는 이 부분에서 부족했던 것 같습니다.

먼저 스티커를 떼는 케이스를 살펴보았습니다.

bottom-up 방식으로, 맨 첫번째 열에서 떼는 것부터 생각을 해 보았지만, 이렇게 하면 다음 값이 이전 어떤 값들에 의해 형성될 수 있는지 생각하기가 어려웠습니다.

그래서 top-down 방식으로, 가장 마지막 열부터 시작해서, 이 칸은 앞서 어떤 칸들에 의해 올 수 있었을까?로 생각하게 되었습니다.

  • 맨 마지막 열의 두 번째 행의 예시를 보겠습니다. 그림에서 초록색 칸을 뗐을 경우는,

    • 바로 직전 대각선 위치의 스티커를 떼고(파란색 1번) 초록색 칸을 뗐거나
    • 전 전 대각선 위치의 스티커를 떼고(파란색 2번) 초록색 칸을 뗐을 경우

    입니다.

  • 즉, …->…->20을 뗀 후 60 을 떼거나, …->…->100을 뗀 후 바로 60을 떼는 경우입니다.
  • 100 밑에 있는 70을 뗐을 때는 살펴보지 않습니다. 왜냐하면, 70을 뗀 후에는 그 윗 대각선의 20을 떼고 60까지 오는 것이 무조건 이득이기 때문이며, 이는 20을 뗀 후 60까지 오는 경우에 속하기 때문에 중복되어 확인하지 않는 것입니다.
  • 즉, 알아보고자 하는 위치의 ‘바로 직전 대각선’ 과 ‘전 전 대각선’이 영향을 미침을 알 수 있습니다.
  • 위 경우에서는 100을 뗀 후 60을 떼는 것이, 20을 떼고 60을 떼는 것의 합보다 크므로(160 > 80) 100을 떼야 합니다. 이로부터, 반드시 직전 대각선에서 오는 것만이 최적의 답은 아님을 알 수 있게 됩니다.

코딩을 하기 위해, dp 배열을 아래와 같이 만듭니다.

이는, 맨 처음열의 50, 30 칸에서 이전 대각선, 전전 대각선을 살펴볼 수 있도록 하기 위함입니다.

이제 모든 과정을 차례대로 진행해 보겠습니다.

[1] 처음 50 에서는 전 대각선과 전전 대각선 중 더 큰 값을 더한다. 모두 0 이므로 그대로 50이다.


[2] 그 다음 30 에서는 전 대각선과 전전 대각선 중 더 큰 값을 더한다. 마찬가지로 그대로 30(30+0)이다.


[3] 그 다음 10은 전 대각선(30)과 전전 대각선(0) 중 더 큰 값을 더한다. 10+30 = 40이 된다.


[4] 그 다음 50은 전 대각선(50)과 전전 대각선(0) 중 더 큰 값을 더한다. 50+50 = 100이 된다.


[5] 그 다음 100은 전 대각선(100)과 전전 대각선(30) 중 더 큰 값을 더한다. 100+100 = 200이 된다.


[6] 그 다음 70은 전 대각선(40)과 전전 대각선(50) 중 더 큰 값을 더한다. 70 + 50 = 120이 된다.


이처럼 같은 과정을 열 끝까지 반복하면, 아래와 같은 결과를 얻을 수 있습니다.

마지막 열의 첫 번째 칸과 두 번째 칸 중 더 큰 값이 문제의 답이 됩니다. (260)


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
int n;
int dp[2][1000002];

int main() {
	
	int T, input;
	scanf("%d", &T);
	
	for (int t = 0; t < T; t++) {
		scanf("%d", &n);

		for (int i = 0; i < 2; i++) {
			for (int j = 2; j < n+2; j++) {
				scanf("%d", &input);
				dp[i][j] = input;
			}
		}

		for (int i = 2; i < n + 2; i++) {		
			for (int j = 0; j < 2; j++) {

				//윗쪽 행이면 대각선은 [j+1][i-1], [j+1][i-2]
				if (j == 0) {
					dp[j][i] = dp[j][i] + max(dp[j + 1][i - 1], dp[j + 1][i - 2]);
				}
				//아랫쪽 행이면 대각선은 [j-1][i-1], [j-1][i-2]
				else if (j == 1) {
					dp[j][i] = dp[j][i] + max(dp[j - 1][i - 1], dp[j - 1][i - 2]);
				}
			}		
		}

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

	return 0;
}