[DP] BOJ 11055번 가장 큰 증가 부분 수열 - 오답노트

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

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

- 문제 파악

N개의 수열이 주어진다. 주어진 수열로 증가하는 부분 수열을 만들수 있는데, 그 수열들 중 합이 제일 큰 값을 출력하라.

 

- 나의 접근

이전에 증가 부분 수열에 관한 문제를 두문제나 풀어 놓고 같은 유형의 문제를 다시 틀렸다. (제대로 복습을 안했겠지)

이중for문 까진 생각했지만, 점화식을 이끌어내는 부분에서 막혔다.

 

정답 알고리즘과 비슷한 아이디어였는데, 나는 기준을 다음 요소로 두었다

예를들어 첫번째 요소에서 두번째 요소를 더 할지 말지를 정할때 두번째 요소와 첫번째 요소를 비교했다.

i를 더 할지 말지, 또는 i가 제일 클지 안 클지 이런것을 고민하느라 제대로 점화식을 이끌어내지 못했다.

 

- 정답

D[i]는 i 번째 요소를 마지막으로 하는 증가하는 수열을 만들었을 때 수열의 합의 최대 값이다.

따라서 i번째 기준이 있어야하고 그 기준까지 증가하는 수열을 만들어야 하므로 이중 for문이 필요하다.

또, 마지막으로 오는 요소값(arr[i]) 보다 작은 값만이 올 수 있다.

 

내가 우려했던 증가하는 수열을 만들때 어떤 수는 선택하고 어떤 수는 선택하지 않을 지를 대소비교를 통해서 해결할 수 있다.

 

D배열의 값은 이미 증가하는 수열을 만들 수 있는 모든 경우의 수중에서 가장 큰 값을 가지고 있다.

그러므로 D[i]에 최대값을 넣을 때는 i 이전에 있던 D배열의 값들중 하나와 현재 요소값을 비교하면 된다.

 

#include "bits/stdc++.h"

using namespace std;

int n;
int D[1001];
int arr[1001];
int ans = 1;


int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	for (int i = 0; i < n; i++)
	{
		D[i] = arr[i];
		for (int j = 0; j < i; j++)
			if (arr[i] > arr[j])
				D[i] = max(D[j] + arr[i], D[i]);
			
		

		ans = max(D[i], ans);

	}

	cout << ans;

}