백준 2094 강수량

사용한 알고리즘: Brute Force (완전탐색)

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

위 3가지 조건을 만족하는지 여부에 따라 true, maybe, false 를 출력하는 문제였습니다.
주어지지 않은 년도가 있고, 이를 잘 가정해서 위 조건을 만족하면 maybe 입니다.

참고로 원문에 "note that the amount of rain during a year can be any nonnegative integer, the limitation on ri is just a limitation on the input" 라는 내용이 있다고 합니다. 강수량이 0 일 수도 있는 것 같습니다. (사실 저는 강수량 0 인 경우를 생각 안했는데 accepted 받았습니다... )

풀이과정은 다음과 같습니다.
(1) <년도, 강수량> 을 pair 로 벡터에 저장해 둡니다.

(2) 벡터를 둘러보며 시작년도, 끝년도 강수량과 그 중간의 강수량의 최대값을 각각 체크해두고, 중간에 빠진 년도가 있는지(maybe 여부 판단) 체크합니다.

(3) 저는 1. 애초에 조건을 만족안하는 경우, 2. 시작,끝년도가 연속된 년도인지, 3. 시작이나 끝 년도의 값이 최소 강수량 (1이라고 생각했습니다...)인 경우, 4. 모르는 값이 잇는경우, 5. 중간에 빠진 년도가 있는경우 로 나누어 모든 경우를 일일히 따져주었습니다.

	#include <bits/stdc++.h>
	using namespace std;
	#define pii pair<int, int>
	const int MAX = 1<<16;
	const int INF = 1000000000;
	int N, M;
	vector<pii> arr;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; ++i){
	int y, r;
	cin >> y >> r;
	arr.push_back(pii(y,r));
	}
	cin>>M;
	for (int i = 0; i < M; ++i){
	int y, x;
	int Y = -1;
	int X = -2;
	// 중간 년도 값들의 최대 저장
	int Between = -1;
	bool ValueY = false;
	bool ValueX = false;
	// 모든 년도 값들이 다 있는지 체크
	bool NOTALL = false;
	int cnt = 0;
	cin >> y >> x;
	for (int j = 0; j < arr.size(); ++j){
	if(arr[j].first < y) continue;
	else if(arr[j].first == y){
	Y = arr[j].second;
	ValueY = true;
	}
	else if(arr[j].first > y && arr[j].first < x){
	Between = max(Between,arr[j].second);
	cnt++;
	}
	else if(arr[j].first == x){
	X = arr[j].second;
	ValueX = true;
	break;
	}
	else break;
	}
	if(cnt<x-y-1) NOTALL = true;
	// 애초에 조건 만족 안하는 경우
	if((ValueX&&Between>=X) || (ValueY&&Between>=Y) || (ValueX&&ValueY&&X>Y)){
	cout << "false" << '\n';
	continue;
	}
	// x,y 가 연속된 년도인 경우
	if(y+1==x){
	// X==Y==1 인 경우도 걸러짐..!
	if(ValueX&&ValueY) cout << "true" << '\n';
	else cout << "maybe" << '\n';
	continue;
	}
	// 아래는 x,y 가 연속되지 않은 경우만 남음
	// x나 y년도 값이 1(최소) 인경우
	if(X==1 || Y==1){
	cout << "false" << '\n';
	continue;
	}
	// 모르는 값이 있는 경우
	if(NOTALL||!ValueX||!ValueY){
	cout << "maybe" << '\n';
	continue;
	}
	// 중간에 빠진 년도 있는경우
	if(NOTALL){
	cout << "maybe" << '\n';
	continue;
	}
	cout << "true" << '\n';
	}
	return 0;
	}

view raw BOJ 2094.cpp hosted with ❤ by GitHub