백준 14002번 가장 긴 증가하는 부분수열 4

1. 가장 긴 증가하는 부분수열의 길이를 구하는 아이디어

2. 이를 활용해 가장 긴 증가하는 부분수열을 구하는 아이디어

3. 코드

#include <stdio.h>

int main()
{
	int i, j, N;
	int array[1000];
	int brray[1000];
	int crray[1000];
	int max;
	int max_index;

	scanf("%d", &N);
	
	for (i = 0; i < N; i++)
	{
		scanf("%d", &array[i]);
	}

	brray[0] = 1;

	for (i = 1; i < N; i++)
	{
		max = 0;
		for (j = 0; j < i; j++)
		{
			if (array[j] < array[i])
			{
				if (max < brray[j])
				{
					max = brray[j];
				}
			}
		}
		brray[i] = max + 1;
	}

	max = 0;

	for (i = 0; i < N; i++)
	{
		if (brray[i] > max)
		{
			max = brray[i];
			max_index = i;
		}
	}

	crray[max - 1] = array[max_index];

	for (i = max - 1; i >= 1; i--)
	{
		for (j = max_index -1; j >= 0; j--)
		{
			if (array[j] < array[max_index] && brray[j] == i)
			{
				max_index = j;
				break;
			}
		}
		crray[i - 1] = array[max_index];
	}

	printf("%d\n", max);

	for (i = 0; i < max; i++)
	{
		printf("%d ", crray[i]);
	}
	
	return 0;
}

얻은 것:

처음에 가장 긴 증가하는 부분수열의 길이를 구하는 문제를 먼저 풀었는데

DP중에서 이 문제처럼 특정 기준을 만족하는 최댓값을 가져와서 푸는 문제들이 여럿 있었다.

그런 것을 많이 풀었음에도 불구하고 처음에 '길이'에 집중해야 하는데 가장 긴 증가하는 부분 수열을 구하는 것 자체에 집중한게 꼬임의 원인이었던 것 같다.

무엇을 구해야 하는지 잘 생각해보는게 늘 중요한 듯하다.

(보너스) 이 아이디어를 활용하여 풀 수 있는 문제 중에 줄세우기가 있다.

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

아이들의 번호 중 가장 긴 증가하는 부분수열의 길이를 찾으면
나머지 아이들은 그 가장 긴 증가하는 부분수열을 기준으로 한번에 한명씩 자리를 찾아가면 되므로 N - (가장 긴 증가하는 부분수열의 길이) 를 출력하면 된다.