[BOJ 백준] 강수량(2094) C++

 

링크 : 2094번: 강수량 (acmicpc.net)

2094번: 강수량

 

문제 설명 : 

기상청에서는 매 해마다 그 해에 내린 비의 양을 측정하여 발표하는데, 이를 그 해의 강수량이라 한다. 이를 토대로 사람들은 어느 해에 몇 년 만에 비가 가장 많이 왔다는 식의 이야기를 하곤 한다. 하지만 사람은 자신의 경험과 감각에 의존하여 이야기하기 때문에, 이러한 이야기가 때론 거짓이 되기도 한다. 따라서 당신은, 기상청의 공식적인 측정 결과를 바탕으로 이러한 이야기들의 진실 여부를 가려내려 한다. 때로는 기상청의 공식적인 발표 자료를 구할 수 없기 때문에, 참과 거짓을 가려내지 못하는 경우도 생길 수도 있다.

편의를 위해 사람들의 이야기를 “X년도에는 Y년도 이후 가장 많은 비가 내렸다”는 형태로 한정하기로 하자. 이러한 이야기는 다음의 조건들이 만족될 때 참이 된다.

1. Y년도, X년도, 그리고 그 사이의 모든 년도들의 강수량에 대한 정보가 알려져 있다.
2. X년도의 강수량은 Y년도의 강수량 이하이다.
3. Y < Z < X를 만족하는 모든 Z들에 대해서, Z년도의 강수량은 X년도보다 적다.

강수량에 대한 정보가 알려져 있지 않은 년도에 대해서 강수량을 잘 가정할 경우에 위의 세 조건이 만족된다면, 이러한 경우는 사람들의 이야기가 가능한 경우가 된다. 그 외의 경우는 거짓이 된다.

강수량에 대한 정보와 사람들의 이야기에 대한 정보가 주어졌을 때, 참, 가능, 거짓 여부를 가려내는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 정수 n(1 ≤ n ≤ 50,000)이 주어진다. 다음 n개의 줄에는 두 정수 y(0 ≤ |y| ≤ 1,000,000,000), r(1 ≤ r ≤ 1,000,000,000)이 주어지는데, 이는 y년도의 강수량이 r이라는 의미이다. 이러한 정보는 y가 증가하는 순서대로 주어진다. 그 다음 줄에는 정수 m(1 ≤ m ≤ 10,000)이 주어진다. 그 다음 m개의 줄에는 사람들의 이야기에 대한 정보를 나타내는 두 정수 Y, X(-1,000,000,000 ≤ Y < X ≤ 1,000,000,000)가 주어진다.

출력 : 

m개의 줄에 각 사람들의 이야기에 대한 답을 출력한다. 참일 경우에는 true를, 가능할 경우에는 maybe를, 불가능한 경우에는 false를 출력한다.

 

 

예제 입력 : 

4
2002 4920
2003 5901
2004 2832
2005 3890
2
2002 2005
2003 2005

예제 출력 : 

false
true

 

 

접근법 : 

1) 어떻게 풀 것인가?

구간에 대한 연산 -->  모르는 경우 모른다로 구간 대표값 활용

-> 인덱스드트리 활용 가능

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

C++ 코드 : 

// 강수량 2094 C++
#if 1
#pragma warning(disable:4996)
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

typedef pair<int, int> pii;

int n, m, y, r, infoY, infoX;
int searchMax;

int indexedTree[1 << 17];
int OFFSET;

// first : year  /  second : rain량
vector<pii> rainInfo;
bool xFlag, yFlag;

int max(int a, int b) {
	if (a > b) return a;
	return b;
}

int search(int idx, int l, int r, int xx, int yy);
int solve();

int main() {

	freopen("input.txt", "r", stdin);
	scanf("%d", &n);

	// 오프셋 위치 구하기
	for (OFFSET = 1; OFFSET < n; OFFSET *= 2);

	// 인덱스드 트리 만들기
	for (int i = OFFSET; i < OFFSET + n; i++) {
		scanf("%d %d", &y, &r);
		rainInfo.push_back({ y,r });
		indexedTree[i] = r;
	}
	for (int i = OFFSET - 1; i > 0; i--) {
		indexedTree[i] = max(indexedTree[i * 2], indexedTree[i * 2 + 1]);
	}


	scanf("%d", &m);
	int flag;
	while (m--) {
		scanf("%d %d", &infoY, &infoX);
		flag = solve();
		if (flag > 0) {
			printf("maybe\n");
		}
		else if (flag == 0) {
			printf("true\n");
		}
		else {
			printf("false\n");
		}
	}
}

int search(int idx, int l, int r, int xx, int yy) {
	int mid;
	if (xx > r || yy < l) {
		return 0;
	}
	if (xx <= l && yy >= r) {
		return indexedTree[idx];
	}
	mid = (l + r + 1) / 2;
	return max(search(idx * 2, l, mid - 1, xx, yy), search(idx * 2 + 1, mid, r, xx, yy));
}

int solve() {
	y = lower_bound(rainInfo.begin(), rainInfo.end(), make_pair(infoX, 0)) - rainInfo.begin();
	r = lower_bound(rainInfo.begin(), rainInfo.end(), make_pair(infoY, 0)) - rainInfo.begin();
	
	if (y < n && rainInfo[y].first == infoX) {
		xFlag = true;
	}
	if (r < n && rainInfo[r].first == infoY) {
		yFlag = true;
	}

	// 1. true 경우의 수
	if (xFlag && yFlag && y - r == infoX - infoY) {
		return 0;
	}

	// 2. false 경우의 수 
	if (xFlag && yFlag && rainInfo[y].second > rainInfo[r].second) {
		return -1;
	}
	searchMax = search(1, 1, OFFSET, lower_bound(rainInfo.begin(), rainInfo.end(), make_pair(infoY + 1, 0)) - rainInfo.begin() + 1, y);
	if (xFlag && searchMax >= rainInfo[y].second) {
		return -1;
	}
	if (yFlag && searchMax >= rainInfo[r].second) {
		return -1;
	}
	
	// 3. maybe
	return 1;
}
#endif