[BOJ] 1637 날카로운 눈

문제 링크

 

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

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

f(x) =정수더미에서 x이하의 정수 갯수라고 생각하고, 전체 정수 범위를 [1, end]라고 하자. end는 입력으로 들어오는 값 C들의 최댓값으로 설정한다. f(x)는 N개의 입력값 A, C, B에서 x가 A 이상인 경우에 (x - A) / B + 1을 구한 뒤, 이를 전부 더하면 얻을수 있다.

 

for (i = 0; i < n; i++) {
	if (arr[i][0] <= mid) { // mid가 arr[i][0] 미만인 경우는 mid 이하인 정수 없음
		int tmp = min(mid, arr[i][1]); // mid값이 arr[i][1]을 넘는 경우 대신 arr[i][1] 사용
		sum += (tmp - arr[i][0]) / arr[i][2] + 1; // tmp 이하인 수의 갯수 체크
	}
}

 

이때 f(x)가 짝수라면 [x+1, end] 범위 안에 홀수가 존재하고, 아닐 경우 [start, x] 범위 안에 홀수가 존재한다. x값의 범위는 1 ~ 2,147,483,647 사이이므로 순차탐색으로 구하려면 TLE를 받게 된다. 따라서 O(lgN) 시간 안에 답을 구할 수 있는

이분탐색을 이용하면 이 문제를 풀 수 있으며, 갯수가 홀수인 정수가 존재하지 않을 수도 있으므로 경계조건 start, end에서 한번 더 갯수가 홀수개인 정수가 존재하는지 여부를 체크해준다.

 

전체 코드는 아래와 같다.

 

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
const ll MIN = -1e12;
ll arr[20000][3];
int main() {
	int i, j, n;
	cin >> n;
	ll maxa = MIN;
	for (i = 0; i < n; i++) {
		for (j = 0; j < 3; j++) cin >> arr[i][j];
		maxa = max(maxa, arr[i][1]);
	}
	ll lo = 0, hi = maxa, mid;
	bool chk = false;
	while (lo + 1 < hi) { //이분 탐색
		mid = (lo + hi + 1) >> 1;
		ll sum = 0;
		for (i = 0; i < n; i++) {
			if (arr[i][0] <= mid) { // mid값이 arr[i][0] 미만인 경우는 mid 이하인 정수 없음
				int tmp = min(mid, arr[i][1]); // mid값이 arr[i][1]을 넘는 경우 대신 arr[i][1] 사용
				sum += (tmp - arr[i][0]) / arr[i][2] + 1; // tmp 이하인 수의 갯수 체크
			}
		}
		if (sum % 2) { // 홀수
			hi = mid;
			if (mid == 2) { //경계 조건 체크
				sum = 0;
				for (i = 0; i < n; i++) {
					if (arr[i][0] <= 2) {
						int tmp = min(2LL, arr[i][1]);
						sum += (tmp - arr[i][0]) / arr[i][2] + 1; // tmp 이하인 수의 갯수 체크
					}
				}
				if (sum % 2) {
					hi = 1;
				}
				else chk = 1;
				break;
			}
		}
		else { //짝수
			lo = mid;
			if (lo == maxa - 1) { //경계 조건 체크
				sum = 0;
				for (i = 0; i < n; i++) {
					if (arr[i][0] <= maxa) {
						int tmp = min(maxa, arr[i][1]);
						sum += (tmp - arr[i][0]) / arr[i][2] + 1;
					}
				}
				if (sum % 2) {
					hi = maxa;
				}
				else chk = 1;
				break;
			}
		}
	}

	if (chk) cout << "NOTHING\n"; //홀수 개의 정수 없음
	else { //홀수 개의 정수 있음
		ll num = 0;
		for (i = 0; i < n; i++) {
			if (hi>=arr[i][0] && hi <= arr[i][1] && (hi - arr[i][0]) % arr[i][2] == 0) num++;
		}
		cout << hi << " " << num;
	}
}