[BOJ] 2357 최솟값과 최댓값

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

2357번: 최솟값과 최댓값

문제

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.

여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.

입력

첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.

10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10

출력

M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 최솟값, 최댓값 순서로 출력한다.

5 100
38 100
20 81
5 81

---

어제 구현했던 세그먼트 트리를 조금 수정해서 문제를 풀 수 있었다.

어제는 단순히 합을 해서 저장해도 됐지만

이번엔 주어진 범위에 대해서 값을 두 개를 가지고 있어야 해서 배열을 pair로 바꿔서 사용했다.

이걸 제외하고는 거의 똑같다. +를 min, max로 바꾼 것 밖에 없다.

 

따로 다시 보고 코드를 작성하지는 않았는데 전체적인 코드는 어제 참고한 거랑 상당히 유사하다.

힙이랑 비슷하다보니 구현하는게 아주 어렵지는 않았다.

 

트리 크기에 맞게 메모리를 잡는 게 인상적이어서 따라 해 봤다.

보통 백준 문제는 메모리 제한이 빡빡한 문제가 아니면 넉넉하게 잡는게

습관이 되다보니 이렇게 딱 맞게 잡는 일이 익숙하지는 않다. 

그래도 트리 크기를 알아내는건 금방 생각해냈다.

 

그리고 STL을 많이 사용하다보니 using namespace std를 사용해버렸다 ㅎ

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

#define INF 1000000001

int N, M;

void init(vector<pair<int, int>> &tree, vector<int>& numbers, int start, int end, int node) {
	if (start == end) {
		tree[node].first = tree[node].second = numbers[start];
		return ;
	}

	int mid = (start + end) / 2;

	init(tree, numbers, start, mid, 2 * node);
	init(tree, numbers, mid + 1, end, 2 * node + 1);

	tree[node].first = max(tree[2 * node].first, tree[2 * node + 1].first);
	tree[node].second = min(tree[2 * node].second, tree[2 * node + 1].second);
}

pair<int, int> find(vector<pair<int, int>>& tree, int start, int end, int node, int left, int right) {
	if (left > end || right < start) return make_pair(0, INF);
	if (left <= start && end <= right) return tree[node];
	
	pair<int, int> lpair, rpair;
	int mid = (start + end) / 2;

	lpair = find(tree, start, mid, 2 * node, left, right);
	rpair = find(tree, mid + 1, end, 2 * node + 1, left, right);

	return make_pair(max(lpair.first, rpair.first), min(lpair.second, rpair.second));
}

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

	vector<int> numbers(N);

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

	int h = ceil(log2(N));
	h = (1 << (h + 1));

	vector<pair<int, int>> tree(h);

	init(tree, numbers, 0, N - 1, 1);

	int a, b;
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &a, &b);

		pair<int, int> res = find(tree, 0, N - 1, 1, a - 1, b - 1);

		printf("%d %d\n", res.second, res.first);
	}

	return 0;
}

 

후기)

세그먼트 트리랑 조금 더 가까워진 기분이 든다.

STL을 많이 사용하면 std::를 매번 쓰기는 아주 거지같다.

특히 vector 안에 pair 넣을 때 불편해죽겠다.