[백준 C++] 11055번: 가장 큰 증가하는 부분 수열

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

 

가장 싫은  큰 증가하는 부분 수열이다. dp로 해결하면 되는 문제

 

dp[1001] 선언해주고 수열을 받아올 a[1001]도 선언해준다. 

 

이 문제를 푸는 핵심은 i로 끝나는 가장 큰 증가하는 부분 수열을 dp[i]에 저장해 주는 것이다. 

즉, dp[0]은 a[0]이고 dp[1]은 a[0]와 a[1]을 비교하여 증가한다면 dp[1]에 dp[0] + a[1]를 넣어준다. 마찬가지로 dp[2]은 a[1]와 a[2]을 비교한 뒤 증가하였다면 dp[2]에 dp[1] + a[2]를 넣어준다. 또한 a[2]와 a[0]를 비교한 뒤 증가하였다면 dp[0] + a[2]를 해주고 이전값과 비교하여 최대값을 dp[2]에 저장해준다. 

 

#include <iostream>
#include <algorithm>
#define MAX 1001
using namespace std;
int dp[MAX] = { 0, };
int a[MAX] = { 0, };
int main(int argc, char* argv[])
{
	int n, max1 = 0;
	cin >> n;
 
	for (int i = 0;i < n;i++) {
		cin >> a[i];
	}
 
 
	for (int i = 0; i < n;i++) {
		dp[i] = a[i];
		for (int j = i - 1;j >= 0;j--) {
			if (a[i] > a[j]) {
				dp[i] = max(dp[i],(dp[j] + a[i]));
			}
		}
		max1 = max(max1, dp[i]);
	}
 
	cout << max1;
 
	return 0;
}

 

설명을 잘하는것도 중요하다는 생각이 든다. 하지만 아직까지는 설명량과 학습량은 반비례한다고 생각해서 학습을 더 많이 하고자 한다.