BOJ 10868 : 최솟값

알고리즘 문제 전체 링크

 

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

 

참고
- 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree)
- 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree)

- BOJ 2357: 최솟값과 최댓값

 

 

세그먼트 트리의 노드에 저장된 값은 아래 두 노드 중 작은 값이어야 한다.

isMin 함수를 이용하여 더 작은 값을 판단하여 init을 하면서 tree에 저장한다.

int isMin(int a, int b)
{
	return (a < b) ? a : b;
}

int init(int left, int right, int node)
{
	if (left == right) return tree[node] = arr[left];

	int mid = (left + right) / 2;

	return tree[node]
		= isMin(init(left, mid, node * 2), init(mid + 1, right, node * 2 + 1));
}

 

마찬가지로 특정 구간에 대해 isMin으로 더 작은 값을 판단하면 된다.

이때, 구간을 벗어나는 경우는 주어진 값 중 가장 큰 값을 return 해야 주어진 구간에서 작은 값을 찾을 수 있다.

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

	int mid = (left + right) / 2;

	return isMin(getMin(left, mid, a, b, node * 2), getMin(mid + 1, right, a, b, node * 2 + 1));
}

 

이 문제에서는 구간을 바꾸지 않으므로 update 함수는 필요없다.

 

전체 코드는 다음과 같다.

#include <stdio.h>

int N, M;
int arr[100100];
int tree[400400];

int isMin(int a, int b)
{
	return (a < b) ? a : b;
}

int init(int left, int right, int node)
{
	if (left == right) return tree[node] = arr[left];

	int mid = (left + right) / 2;

	return tree[node]
		= isMin(init(left, mid, node * 2), init(mid + 1, right, node * 2 + 1));
}

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

	int mid = (left + right) / 2;

	return isMin(getMin(left, mid, a, b, node * 2), getMin(mid + 1, right, a, b, node * 2 + 1));
}

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

	for (int i = 1; i <= N; i++) scanf("%d", &arr[i]);

	init(1, N, 1);

	for (int i = 0; i < M; i++)
	{
		int a, b;

		scanf("%d %d", &a, &b);

		printf("%d\n", getMin(1, N, a, b, 1));
	}

	return 0;
}

---

Bottom-Up 방식은 다음과 같다.

 

먼저 tree를 최악의 값으로 모두 변경한다.

start Index를 구하기 위해 n을 구했으므로, 1 << (n + 1)이 모든 tree의 최대 index가 된다.

for (n = 1; (1 << n) <= N; n++);
start = 1 << n;
start--;

int maxTreeIndex = (1 << (n + 1));
for (int i = 0; i <= maxTreeIndex; i++) tree[i] = 0x7fff0000;

 

tree는 들어오는 값과 비교하면서 더 작은 값으로 바꾼다.

int isMin(int a, int b)
{
	return (a < b) ? a : b;
}

void update(int index, int value)
{
	index += start;

	while (index > 1)
	{
		tree[index] = isMin(tree[index], value);

		index /= 2;
	}
}

 

getMin도 ans를 가장 큰 값으로 설정한 후, 가장 작은 값을 구하도록 수정하면 된다.

int getMin(int left, int right)
{
	int ans = 0x7fff0000;

	left += start;
	right += start;

	while (left < right)
	{
		if (left % 2 == 0) left /= 2;
		else
		{
			ans = isMin(ans, tree[left]);
			left += 1;
			left /= 2;
		}

		if (right % 2 == 1) right /= 2;
		else
		{
			ans = isMin(ans, tree[right]);
			right -= 1;
			right /= 2;
		}
	}

	if (left == right) ans = isMin(ans, tree[left]);

	return ans;
}

 

전체 코드는 다음과 같다.

#include <stdio.h>

int N, M;
int tree[400400];
int start;

int isMin(int a, int b)
{
	return (a < b) ? a : b;
}

void update(int index, int value)
{
	index += start;

	while (index > 1)
	{
		tree[index] = isMin(tree[index], value);

		index /= 2;
	}
}

int getMin(int left, int right)
{
	int ans = 0x7fff0000;

	left += start;
	right += start;

	while (left < right)
	{
		if (left % 2 == 0) left /= 2;
		else
		{
			ans = isMin(ans, tree[left]);
			left += 1;
			left /= 2;
		}

		if (right % 2 == 1) right /= 2;
		else
		{
			ans = isMin(ans, tree[right]);
			right -= 1;
			right /= 2;
		}
	}

	if (left == right) ans = isMin(ans, tree[left]);

	return ans;
}

int main()
{
	int n;

	scanf("%d %d", &N, &M);

	for (n = 1; (1 << n) <= N; n++);
	start = 1 << n;
	start--;

	int maxTreeIndex = (1 << (n + 1));
	for (int i = 0; i <= maxTreeIndex; i++) tree[i] = 0x7fff0000;

	for (int i = 1; i <= N; i++)
	{
		int x;

		scanf("%d", &x);

		update(i, x);
	}

	for (int i = 0; i < M; i++)
	{
		int a, b;

		scanf("%d %d", &a, &b);

		printf("%d\n", getMin(a, b));
	}

	return 0;
}