가장 큰 증가 부분 수열 (feat. 백준, 11055번)

가장 큰 증가 부분 수열
https://www.acmicpc.net/problem/11055

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

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/11055
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int N, arr[1001], dp[1001];
	cin >> N;
	for (register int i = 1; i <= N; ++i)
		cin >> arr[i], dp[i] = 0;
	for (register int i = 1; i <= N; ++i) {
		for (register int j = 1; j <= i; ++j)
			if (arr[j] < arr[i])
				dp[i] = max(dp[i], dp[j]);
		dp[i] += arr[i];
	}
	cout << *max_element(dp + 1, dp + 1 + N) << endl;
	return 0;
}
// *&)*@*

1. 예제를 기준으로 설명을 해보겠습니다.
2. 가장 앞부터 시작하여 1은 비교할 대상이 없으므로 자기자신만 해당하여 1을 가집니다. 이로써 1이 갖는 수는 1 입니다.
3. 100은 1보다 크기 때문에 100이 갖는 0과 1이 갖는 1 중 큰값인 1을 취하고 자신을 더해줍니다. 이로써 100이 갖는 수는 101 입니다.
4. 2는 1보다 크기 때문에 2가 갖는 0과 1이 갖는 1 중 큰값인 1을 취하고 자신을 더해줍니다. 이로써 2가 갖는 수는 3 입니다.
5. 50은 2보다 크기 떄문에 50이 갖는 0과 2가 갖는 3 중 큰값인 3을 취하고 자신을 더해줍니다. 이로써 50이 갖는 수는 53 입니다.
6. 60은 50보다 크기 때문에 50이 갖는 53과 60이 갖는 0 중 큰값인 53을 취하고 자신을 더해줍니다. 이로써 60이 갖는 수는 113 입니다.
7. 3은 2보다 크기 때문에 2가 갖는 3과 3이 갖는 0 중 큰값인 3을 취하고 자신을 더해줍니다. 이로써 3이 갖는 수는 6 입니다.
8. 이렇게 N까지 비교한 결과는 1 101 3 53 113 6 11 17 24 32 이고 최대값은 113 입니다.

 

좋아요공감

저작자표시비영리