05.06. 스티커 [Dynamic Programming][백준 9465]

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

9465번: 스티커

 

Algorithm classification : Dynamic Programming

 

05.06.1. Problem

Nancy, your little sister, has a sheet of 2n stickers of rectangular shape that are arranged in 2 rows and n columns. See Figure 1(a). Nancy wants to decorate her desk with the stickers. But the quality of the stickers is poor, and tearing off one sticker from the sheet spoils the stickers sharing an edge with it. So, Nancy must lose the stickers above, below, to the left of, and to the right of the sticker she tears off. 

Figure 1. A sheet of 10 stickers in 2 rows

 

Nancy had no idea about what to do. You looked at her and suggested that she should score each sticker and try to choose a possible set of stickers that maximizes the total score. Nancy marked scores to all the 2n stickers as in Figure 1(b). And Nancy had no idea, again. You again took a look at her and sighed. You cannot help doing something for her, and at last decided to help her with a fast computer program. Your program is to select a set of stickers of maximum total score from the 2n stickers such that no two of them share an edge.

 

In the example shown in Figure 1, the maximum total score is 260 when you select the four stickers of scores 50, 50, 100, 60. Unfortunately, in this case, it is not allowed to simultaneously select both of the two highest scored stickers (of score 100 and 70) because the two stickers share an edge between them. 

 

05.06.2. Input limit

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line that contains an integer (1 ≤ n ≤ 100,000), where 2n is the number of stickers in the sheet. In the next two lines, each line contains n integers, each of which represents Nancy’s score for the sticker at that position in the sticker sheet. Every two consecutive integers in a line are separated by a blank. Note that the 2n stickers are of rectangular shape and are arranged in 2 rows and n columns in the sheet. Nancy’s scores range from 0 to 100. 

 

05.06.3. Output

Your program is to write to standard output. Print exactly one line for each test case. The line should contain the maximum possible total score for a subset of the 2n stickers such that no two stickers share an edge. 

 

05.06.4. Solution

지금까지 소개해드렸던 문제보다 조금 어려워졌습니다. 지금까지는 dp table이 1차원이였다면 이제 2차원으로 넘어왔습니다. 이웃한 스티커는 떼지 못하는 조건으로 스티커를 떼어 스티커 가치의 최대 합을 계산하는 문제입니다. Greedy algorithm으로 풀 수 있을지는 직접 생각해보시면 좋을 것 같습니다.(몇 개의 case를 생각해보시면 좋습니다.)

int a[2][100001] = {0};
int dp[100001][3] = {0};
int i, j, N; 

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

	while(t){
		scanf("%d", &N);
		
		for(i = 0; i < 2; i++){
			for(j = 0; j < N; j++){
				scanf("%d", &a[i][j]);
			}
		}
		for(i = 0; i < N; i++){
			dp[i+1][0] = max(dp[i][0], max(dp[i][1], dp[i][2]));
            dp[i+1][1] = max(dp[i][0], dp[i][2]) + a[0][i];
            dp[i+1][2] = max(dp[i][0], dp[i][1]) + a[1][i];
		}

		printf("%d\n", max(dp[N][0], max(dp[N][1], dp[N][2]))); 
		
		for(i = 0; i < 100001; i++){
			for(j = 0; j < 3; j++){
				dp[i][j] = 0;
			}
		}
		t--;
	}
	
	
	return 0;
}

조금 복잡해진 것 같지 않으신가요. 점화식 또는 dp table을 정의하는 것이 가장 중요합니다. dp[i][j]로 둔다면 dp[i][0]은 i번째 열에서 스티커를 선택하지 않는 경우 dp[i][1]은 i번째 열에서 상단의 스티커를 선택하는 경우 dp[i][2]는 i번째 열에서 하단의 스티커를 선택하는 경우로 두겠습니다. 이때 dp[i][0] 즉, i번째 열에서 선택하지 않는 경우가 답에 가까워 질 수 있다는 점을 보아하니 greedy algorithm으로 해결하기 어렵다는 것을 눈치채실 수 있습니다. 최종적으로 구하게 되는 것은 data가 주어졌을 때, 

 

max(dp[n][0], dp[n][1], dp[n][2])

 

입니다. 참고로 2차원 배열은 fill function을 사용할 수 없습니다.

 

Top-down방식으로 구현하려면 argument로 dp table의 i와 j를 넘기면 될 것입니다. 개인적으로 이 문제는 top-down방식보다 buttom-up방식이 쉬웠습니다. 시간복잡도와 공간복잡도는 살펴보면 n개의 열을 가진 data가 주어질때 풀어야 하는 부분 문제의 수는 O(3n)이고 하나의 부분 문제를 해결할 때 O(1)이 필요하므로 시간복잡도와 공간복잡도 모두 O(n)입니다.