[백준/BOJ] 백준 1637번 : 날카로운 눈

www.acmicpc.net/problem/1637

1637번: 날카로운 눈

이분 탐색을 이용해서 mid숫자까지 전체 개수 누적합을 구하고, 전체 개수 누적합이 홀수 이면 홀수개 존재하는 정수가 1~mid사이 범위 안에 존재하는 것을 이용해서 문제를 해결했다.

 

코드

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

int n;
vector<long long> a;
vector<long long> c;
vector<long long> b;

//number까지의 전체 개수 누적합을 구한다
//전체 개수 누적합이 홀수 이면 홀수개 존재하는 정수가 1~number사이 범위 안에 존재하는것이다
long long Csum(long long number)
{
	long long cnt = 0;

	for (int i = 0; i < n; i++)
	{
		long long i_max_number = c[i];

		//i번째 구간의 최대 숫자 이내의 숫자까지의 개수만 구할 수 있다
		long long check_number = min(number, i_max_number);

		long long this_cnt;

		//확인하는 숫자가 i번째 구간에 없는 수 일때
		if (check_number < a[i])
			this_cnt = 0;

		else
			this_cnt = ((check_number - a[i]) / b[i]) + 1;

		cnt += this_cnt;
	}

	return cnt;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		long long input_a, input_c, input_b;

		cin >> input_a >> input_c >> input_b;

		a.push_back(input_a);
		c.push_back(input_c);
		b.push_back(input_b);
	}

	long long left = 1;
	long long right = 2147483647;
	long long result_number = -1;
	long long result_cnt;

	while (left <= right)
	{
		long long mid = (left + right) / 2;

		//mid숫자 까지 전체 개수 누적합을 구한다
		//전체 개수 누적합이 홀수 이면 홀수개 존재하는 정수가 1~mid사이 범위 안에 존재하는것이다
		long long Csum_cnt = Csum(mid);

		if (Csum_cnt % 2 == 1)
		{
			result_number = mid;

			right = mid - 1;
		}

		else
		{
			left = mid + 1;
		}
	}

	if (result_number == -1)
		cout << "NOTHING";

	else
	{
		result_cnt = Csum(result_number) - Csum(result_number - 1);

		cout << result_number << " " << result_cnt;
	}

	return 0;
}