05.15. 가장 큰 증가 부분 수열 [Dynamic Programming][백준 11055]

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

11055번: 가장 큰 증가 부분 수열

 

Algorithm classification : Dynamic Programming

 

05.15.1. Problem

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

 

05.15.2. Input limit

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

05.15.3. Output

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

 

05.15.4. Solution

DP table을 어떻게 정의하느냐에 따라 구현이 달라질 수 있습니다.

 

DP table[i] = i번째 항부터 시작하는 합이 가장 큰 증가 부분 수열의 합

DP table[i] = i번째 항을 마지막으로 하는 합이 가장 큰 증가 부분 수열의 합

 

개인적으로는 2번째 정의가 풀기 더 수월한 것 같습니다. DP table을 어떻게 채워냐가느냐의 차이이니 두가지 경우 다 작성해보시는 것도 좋을 듯 합니다. 최종적으로 DP table의 정의에 따라 DP table 값 중 최대값을 출력해주시면 됩니다.

	for(i = 0 ; i < n; i++){
		scanf("%d", &a[i]);
		dp[i] = a[i];
	}
	
	
	for(i = 0; i < n; i++){
		for(j = 0; j < i; j++){
			if(a[j] < a[i]) dp[i] = max(dp[i], dp[j] + a[i]);
		}
	}
	
	int ans = 0;
	for(i = 0; i < n; i++){
		ans = max(ans, dp[i]);	
	}
	
	printf("%d", ans);

한가지 특이한 점은 부분 문제를 해결하는데 O(N)의 시간복잡도가 소요된다는 점입니다. index를 기점으로 남은 항들을 둘러보며 최댓값을 계산해나가기 때문입니다. 따라서 시간복잡도는 O(N^2)입니다.

 

이 문제를 해결하신다면 가장 긴 증가하는 부분수열을 계산하는 문제인 백준 11053번 문제는 쉽게 해결하실 수 있습니다. DP table의 정의는 유사할 것이고 index를 기점으로 남은 항들을 둘러보며 가장 긴 증가하는 부분수열을 계산하는 방식(DP table update 조건 검사) 또한 같을 것입니다. 차이점은 DP table의 초기값 및 update 값 뿐입니다. 위의 code에서 단 2줄만 수정해주시면 됩니다.

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

 

 

추가로 가장 큰 증가 부분 수열의 test case를 남겨두도록 하겠습니다.

6
1 5 6 2 3 4
>> 12

5
50 40 30 20 10
>>50

5
10 90 20 80 100
>> 210
 
1
1
>> 1
 
15
115 5 82 81 63 130 80 93 122 81 58 25 63 66 22
>> 363

20
97 112 16 129 25 87 15 75 85 65 117 143 133 83 59 30 111 24 70 128
>> 481
 
10
2 11 3 14 1 200 100 5 101 13
>> 228

 

하나의 test case를 통해 알고리즘을 설명해드리자면 아래의 table과 같이 DP table을 update합니다.

	1	5	6	2	3	4
초기화	1	5	6	2	3	4
i == 0	1	5	6	2	3	4
i == 1	1	6	6	2	3	4
i == 2 j == 0 j == 1	1	6	11 7 11
...
i == 5 j == 0 j == 1 j == 2 j == 3 j == 4						10 5 5 5 7 10