[실버2] [C++] 11053번: 가장 긴 증가하는 부분 수열

링크

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

11053번: 가장 긴 증가하는 부분 수열

문제

입출력 예제

코드

#include <iostream>
#include <algorithm>

using namespace std;

int nums[10001];
int dp[10001];

int main(void)
{
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> nums[i];
	}

	dp[0] = 1;

	int answer = dp[0];

	for (int i = 1; i < n; i++)
	{
		int maxDp = 0;
		for (int j = 0; j < i; j++)
		{
			// 더 작은 수 중에, 현재 카운팅 된 최대로 이어진 부분 수열보다 큰 경우
			if (nums[j] < nums[i] || dp[j] > maxDp)
				maxDp = dp[j];					
		}
		dp[i] = maxDp + 1;	// 자기 자신까지 포함하니 카운팅 + 1
		answer = max(dp[i], answer);
	}

	cout << answer;
}

풀이

DP를 이용하여 풀이한 문제 입니다.

 

2중 for문을 이용하여, 자신과 자신보다 이전에 나온 수를 비교합니다.

그 수가 자신보다 작은 수라면, 그 수 까지 카운팅된 최대 행렬을 저장합니다.(현재 카운팅 된 수 보다 클 경우에만)

 

for문이 끝났다는 것은 자기 자신까지 왔다는 것 이므로 카운팅 된 수에 +1 을 해 주면 현재 수 까지 카운팅 될 수 있는 가장 큰 이어진 부분 수열의 수가 될 것입니다.

 

그림으로 설명하자면 다음과 같은 경우, 맨 처음 1의 카운트(DP) 값은 1 입니다.

2중 for문에 의해서 2를 기준으로 카운팅 시작하면, 2보다 이전에 나온 수인 1을 가져와 비교합니다.
1은 2보다 작으므로, 최대 행렬을 1로 저장하고 for문이 끝나면 자기 자신을 포함해서 자신의 카운트 값을 2로 설정합니다.

해당 과정을 반복하면 5까지는 별 문제 없이 카운팅을 4까지 채울 수 있을 것 입니다.
이후, 2를 기준으로 검사할 때 자신보다 작은 수가 1밖에 없으니 카운팅은 1에서 끝날 것이고
최종 카운팅은 자기 자신을 포함한 2가 될 것입니다.

해당 과정을 모두 끝내면 다음과 같이 DP가 완성되고,
최대 카운트를 4로 답을 출력하게 됩니다.