BOJ 2357 : 최솟값과 최댓값

알고리즘 문제 전체 링크

 

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

 

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

- BOJ 10868 : 최솟값

 

 

BOJ 10868에서 답을 구한 방법으로 최솟값을 구할 수 있고, 응용하면 최댓값도 구할 수 있다.

따라서 세그먼트 트리를 2개 이용하면 된다.

 

하지만 구조체로 묶으면 조금 더 간편하다.

TREE 라는 구조체를 선언해서 min과 max를 동시에 관리한다.

typedef struct st
{
	int min;
	int max;
}TREE;

 

init에는 leftTree와 rightTree에서 각각 더 작은 값과 더 큰 값을 갱신하면 된다.

TREE init(int left, int right, int node)
{
	if (left == right)
	{
		tree[node].min = tree[node].max = arr[left];
		return tree[node];
	}

	int mid = (left + right) / 2;

	TREE leftTree = init(left, mid, node * 2);
	TREE rightTree = init(mid + 1, right, node * 2 + 1);

	tree[node].min = isMin(leftTree.min, rightTree.min);
	tree[node].max = isMax(leftTree.max, rightTree.max);

	return tree[node];
}

 

getTree도 마찬가지로 적용하면 된다.

전체 코드를 참고하자.

#include <stdio.h>

int N, M;
int arr[100100];

typedef struct st
{
	int min;
	int max;
}TREE;

TREE tree[400400];

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

int isMax(int a, int b)
{
	return (a > b) ? a : b;
}

TREE init(int left, int right, int node)
{
	if (left == right)
	{
		tree[node].min = tree[node].max = arr[left];
		return tree[node];
	}

	int mid = (left + right) / 2;

	TREE leftTree = init(left, mid, node * 2);
	TREE rightTree = init(mid + 1, right, node * 2 + 1);

	tree[node].min = isMin(leftTree.min, rightTree.min);
	tree[node].max = isMax(leftTree.max, rightTree.max);

	return tree[node];
}

TREE getTree(int left, int right, int a, int b, int node)
{
	if (b < left || right < a)
	{
		TREE ret = { 0 };
		
		ret.min = 0x7fff0000;

		return ret;
	}

	if (a <= left && right <= b) return tree[node];

	int mid = (left + right) / 2;

	TREE leftTree = getTree(left, mid, a, b, node * 2);
	TREE rightTree = getTree(mid + 1, right, a, b, node * 2 + 1);

	TREE ret;

	ret.min = isMin(leftTree.min, rightTree.min);
	ret.max = isMax(leftTree.max, rightTree.max);

	return ret;
}

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);

		TREE tmp = getTree(1, N, a, b, 1);

		printf("%d %d\n", tmp.min, tmp.max);
	}

	return 0;
}

---

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

주어지는 정수가 1 이상이기 때문에 max 값을 음수로 변경하지는 않는다.

#include <stdio.h>

int N, M;

typedef struct st
{
	int min;
	int max;
}TREE;

TREE tree[400400];
int start;


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

int isMax(int a, int b)
{
	return (a > b) ? a : b;
}

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

	while (index > 1)
	{
		tree[index].min = isMin(tree[index].min, value);
		tree[index].max = isMax(tree[index].max, value);

		index /= 2;
	}
}

TREE getTree(int left, int right)
{
	TREE ans;

	ans.min = 0x7fff0000;
	ans.max = 0;

	left += start;
	right += start;

	while (left < right)
	{
		if (left % 2 == 0) left /= 2;
		else
		{
			ans.min = isMin(ans.min, tree[left].min);
			ans.max = isMax(ans.max, tree[left].max);

			left += 1;
			left /= 2;
		}

		if (right % 2 == 1) right /= 2;
		else
		{
			ans.min = isMin(ans.min, tree[right].min);
			ans.max = isMax(ans.max, tree[right].max);

			right -= 1;
			right /= 2;
		}
	}

	if (left == right)
	{
		ans.min = isMin(ans.min, tree[left].min);
		ans.max = isMax(ans.max, tree[left].max);
	}

	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].min = 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);

		TREE tmp = getTree(a, b);

		printf("%d %d\n", tmp.min, tmp.max);
	}

	return 0;
}