BOJ 12015 : 가장 긴 증가하는 부분 수열 2

알고리즘 문제 전체 링크

삼성 B형 전체 링크

 

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

 

참고

- BOJ 1655 : 가운데를 말해요 with 세그먼트 트리

 

 

수열 A의 크기는 1,000,000이고 들어 있는 값은 1부터 1,000,000이므로 세그먼트 트리를 이용해서 문제를 풀 수 있다.

 

예제의 {10, 20, 10, 30, 20, 50}에서

가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)의 길이 4를 찾아보자.

 

수열에 값이 하나가 추가될 때마다, LIS의 길이를 세그먼트 트리를 이용해서 갱신하면 문제를 풀 수 있다.

값 x가 추가되고, 구간 [1, x - 1]의 LIS의 길이가 y라면 구간 [1, x]의 LIS의 길이는 y + 1이 된다.

이때 세그먼트 트리의 [x, x]에 y + 1을 갱신하는 방식으로 LIS의 길이를 구할 수 있다.

 

수열의 첫 번째는 10이기 때문에 세그먼트 트리의 10에 해당하는 구간을 업데이트해야 한다.

10이 추가 될 때 LIS의 길이는 세그먼트 트리에서

구간 [1, 10 - 1]에서 LIS의 길이에 1을 더하면 된다.

하지만, 10은 첫 번째로 들어온 숫자이기 때문에 [1, 10 - 1] = [1, 9] 구간에서 LIS가 없으므로, LIS의 길이는 0이 된다.

즉, [1, 10]에서 LIS의 길이는 0 + 1이 되고, 이 값을 구간 [10, 10] 에 1로 세그먼트 트리에 업데이트한다.

 

수열의 두 번째는 20이다.

[1, 20 - 1]에서 LIS의 길이는 [10, 10] = 1이 된다.

즉, 20이 추가되면서 {10} → {10, 20} 의 LIS의 길이는 1 + 1이 된다.

따라서, 구간 [20, 20]에 2로 세그먼트 트리에 업데이트한다.

 

수열의 세 번째는 다시 10이다.

구간 [1, 10 - 1]에서 LIS의 길이는 여전히 0이다.

따라서, 구간 [10, 10]은 0 + 1로 다시 업데이트면 된다.

 

수열의 네 번째는 30이다.

구간 [1, 30 - 1]에서 가장 큰 값은 구간 [20, 20]에 의해 2가 된다.

즉, {10, 20, 10}에 30을 추가하면 LIS의 길이는 2 + 1이 된다.

따라서, 구간 [30, 30]에 3을 세그먼트 트리에 업데이트한다.

 

수열의 다섯 번째는 20이다.

구간 [1, 20 - 1]에서 가장 큰 값은 [10, 10]에 의해 1이 된다.

따라서, 구간 [20, 20]은 1 + 1을 다시 업데이트한다.

 

수열의 마지막은 50이다.

구간 [1, 50 - 1]에서 가장 큰 값은 구간 [30, 30]에 의해 3이 된다.

따라서, 구간 [50, 50]에 3 + 1을 세그먼트 트리에 업데이트한다.

 

수열로 주어지는 숫자는 값이 최대 1,000,000이므로,

[1, 1,000,000] 에서 가장 큰 값은 [50, 50]에 의해 4가 된다.

---

세그먼트 트리의 update를 이용해서 구간에서 LIS의 길이를 갱신한다.

void update(int left, int right, int node, int index, int value)
{
	if (index < left || right < index) return;

	if (left == right)
	{
		tree[node] = value;
		return;
	}

	int mid = (left + right) / 2;
	int leftNodeIndex = node * 2;
	int rightNodeIndex = node * 2 + 1;

	update(left, mid, leftNodeIndex, index, value);
	update(mid + 1, right, rightNodeIndex, index, value);

	int leftValue = tree[leftNodeIndex];
	int rightValue = tree[rightNodeIndex];

	tree[node] = (leftValue > rightValue) ? leftValue : rightValue;
}

 

그리고 주어진 구간 [a, b] 내에 가장 큰 값은 getMax를 이용해서 찾을 수 있다.

즉, [a, b]에서 LIS의 길이를 찾는다.

int getMax(int left, int right, int a, int b, int node)
{
	if (b < left || right < a) return 0;
	if (a <= left && right <= b) return tree[node];

	int mid = (left + right) / 2;

	int leftValue = getMax(left, mid, a, b, node * 2);
	int rightValue = getMax(mid + 1, right, a, b, node * 2 + 1);

	return (leftValue > rightValue) ? leftValue : rightValue;
}

 

value가 구간에 추가된다면,

getMax를 이용해 전체 구간 [1, 1,000,000] 중 [1, value -1]에서 LIS의 길이를 찾는다.

int max = getMax(1, 1000000, 1, value - 1, 1);

 

구간 [1, value - 1] 까지 LIS의 길이는 max가 되기 때문에,

value가 추가되면 value를 포함하는 구간 [1, value]의 LIS의 길이는 max + 1이 된다.

update(1, 1000000, 1, value, max + 1);

 

모든 수열에 대해 LIS의 길이를 갱신하고, 마지막에 전체 구간의 LIS의 길이를 출력하면 된다.

printf("%d\n", getMax(1, 1000000, 1, 1000000, 1));

 

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (50000 + 500000)

int N;
int tree[4004000];

void update(int left, int right, int node, int index, int value)
{
	if (index < left || right < index) return;

	if (left == right)
	{
		tree[node] = value;
		return;
	}

	int mid = (left + right) / 2;
	int leftNodeIndex = node * 2;
	int rightNodeIndex = node * 2 + 1;

	update(left, mid, leftNodeIndex, index, value);
	update(mid + 1, right, rightNodeIndex, index, value);

	int leftValue = tree[leftNodeIndex];
	int rightValue = tree[rightNodeIndex];

	tree[node] = (leftValue > rightValue) ? leftValue : rightValue;
}

int getMax(int left, int right, int a, int b, int node)
{
	if (b < left || right < a) return 0;
	if (a <= left && right <= b) return tree[node];

	int mid = (left + right) / 2;

	int leftValue = getMax(left, mid, a, b, node * 2);
	int rightValue = getMax(mid + 1, right, a, b, node * 2 + 1);

	return (leftValue > rightValue) ? leftValue : rightValue;
}

int main()
{
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		int value;

		scanf("%d", &value);

		int max = getMax(1, 1000000, 1, value - 1, 1);
		update(1, 1000000, 1, value, max + 1);
	}

	printf("%d\n", getMax(1, 1000000, 1, 1000000, 1));

	return 0;
}