ShaShaKa Dev Note

가장 긴 증가하는 부분 수열

28 July 2019

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

이번은 LIS(Longest Increasing Subsequence)를 구하는 문제를 풀어보도록 하겠습니다.

#include<stdio.h>

void updateArr(int val);

static int* arr;
static int arr_idx = 0;

int main(void) {

	int N, val;
	scanf("%d", &N);

	arr = new int[N + 1];
	arr[0] = 0;

	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &val);
		if (val > arr[arr_idx])
		{
			arr_idx++;
			arr[arr_idx] = val;
		}
		else if (val < arr[arr_idx]) {
			updateArr(val);
		}
	}

	printf("%d", arr_idx);

	return 0;
}

void updateArr(int val) {
	int num = arr_idx;

	while (num > 0 && arr[num] > val )
	{
		if (val < arr[num] && val > arr[num -1])
		{
			arr[num] = val;
			return;
		}
		num--;
	}
}

먼저 아래 예와 같은 상황을 보도록 하겠습니다.
이 문제에서는 가장 긴 수열의 길이만 찾으면 되므로 해당 수열의 정확한 모양은 찾지않아도 됩니다.
만약, {1,3,4,2,3,4,5}의 수열이 있다고 가정해봅시다.
최대 길이의 수열을 찾는다고 하면 아래 순서와 같이 가정할 수 있습니다.
{1} => {1,3} => {1,3,4} : 현재까지의 최대 길이는 3입니다.
이 다음에 등장하는 수는 2이고, 이 다음부터는 3이 나와도 새로이 수열 연결이 가능합니다.
따라서, {1,3,4} + 2 => {1,2,4}로 바꾸어주어도 현재의 최대 길이는 변함이 없습니다.
그 다음부터는 {1,2,4} + 3 => {1,2,3} : 이제부터는 4가 나오면 최대 수열의 길이가 늘어나게 됩니다.
{1,2,3} + 4 => {1,2,3,4}
{1,2,3,4} + 5 => {1,2,3,4,5} 로 변형이 되어 최대 길이는 5가 됩니다.
중간에 수열의 모양이 변경이 되기 때문에, 정확한 수열의 모양은 알 수 없지만 최대 길이는 체크가 가능합니다.
해당 로직을 수행하면서, arr_idx의 값을 업데이트해주고 마지막에 return해주도록 합니다.