boj, 백준) 1637. 날카로운 눈 (C/C++)

1. 문제 링크

www.acmicpc.net/problem/1637

1637번: 날카로운 눈

2. 문제 개요

정수더미 속에서 날카로운 눈을 이용해 홀수개 존재하는 정수를 찾아야 하는 문제이다. 근데, 정수더미 안에 정수가 적게 있으면 문제가 너무 쉬워지게 된다. 그래서, 정수더미안에 정수를 무지막지하게 많이 넣기로 했다. 정수더미가 주어졌을 때, 그 안에 홀수개 존재하는 정수를 찾는 프로그램을 작성해보자.

 

3. 문제 힌트

정말 간단하게 생각해보자.

 

숫자의 범위는 1 ~ 2,147,483,647이다. (2^31-1)

배열을 2,147,483,647개 만들어서 출현 횟수를 모두 다 가지고 있는 것이다.

 

우선, 입력이 최대 2만개이다.

1 2147483647 1 과 같은 입력이 2만 개 들어오면, 21억 번 2만 번 1씩 접근해야 하기 때문에 시간이 상당히 오래 걸리는 것을 알 수 있다.

 

아주 양보해서, 배열 21억 개를 들고 모두 카운트했다 해도, 정답을 찾기 위해서 1~21억 번의 인덱스까지 모두 1번 순회해야 하는데 이것도 많은 시간이 걸리는 것을 알 수 있다.

 

 

 

자, 그러면 모든 숫자를 저장해 두지 않고 답을 구해야 한다.

 

숫자의 범위로 계산하면 좋을 것 같은 느낌이 든다.

단 하나의 숫자만 홀수이기 때문에, 홀수가 속한 범위의 개수의 합은 홀수가 될 것이고, 홀수가 속하지 않은 곳의 범위의 개수의 합은 짝수가 될 것이다.

 

(홈페이지의 힌트에도 이분탐색이라고 되어있는데, 어떠한 숫자를 정하고(mid) 그 값으로 어떤 동작을 취한 뒤, mid의 값을 크게 할 것인지, 작게 할 것인지 결정하는 부분이 필요하다)

 

4. 문제 풀이

위, bold체로 적은 부분을 고려해서 문제를 풀어보자. 어떠한 숫자(mid)를 결정했다.  [1, mid]범위의 숫자의 개수의 합이 짝수라면, [1, mid]에는 개수가 홀수인 숫자가 없다.

 

그래서, mid를 left+ 1로 할당한다.

 

그러지 않고 [1, mid]범위의 숫자의 개수의 합이 홀수인 경우, 해당 범위에 개수가 홀수인 숫자가 포함되어 있고, 적어도 mid보다 작기 때문에, 우선 mid를 저장한 뒤, mid를 right - 1로 할당한다.

 

 

자, 결정된 mid를 가지고 어떤 동작을 취해야 할까?

 

N이 20,000개다. 

 

A C B의 숫자가 들어왔을 때, A C B로 생기는 정수 중 빠르게 mid보다 작은 숫자들의 개수를 세어야 한다. 

A C B로 만들어지는 정수는 문제에 있듯이, A + kB ≤ C이고, 여기서 0≤k이다.

자 그럼 k를 구하기 위해 이항을 해보면, 

k ≤ (C-A)/B 가 된다. k는 내림(floor) 해야 하고, k는 0부터 시작하기 때문에 숫자의 개수는 k+1개가 되고, (C-A)가 음수라면 0으로 처리해야 한다.

 

우리는 A C B 모두 알고 있기 때문에 A C B로 입력되는 하나의 query에 대해서 O(1)의 속도로 개수(k)를 찾을 수 있다.

이렇게 N개의 query에 대해서 숫자의 개수를 다 구한 뒤, 이분탐색을 통해 범위를 좁혀나가는 것이다.

 

따라서 시간 복잡도는 O(NlogX)이고, X는 숫자의 범위이다.(최대 1~2^31-1) 

5. 코드

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

struct ITEM {
	int a, c, b;
};

int n, ans = -1;
ITEM arr[20000];

long long solution(long long mid)
{
	if (mid == 0) return 0;

	long long sum = 0;

	for (int i = 0; i < n; ++i)
	{
		long long num = 0;
		long long val = min((long long)arr[i].c, mid) - arr[i].a;
		num = val < 0 ? 0 : val / arr[i].b + 1;
		sum += num;
	}

	return sum;
}

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

	for (int i = 0; i < n; ++i)
		scanf("%d %d %d", &arr[i].a, &arr[i].c, &arr[i].b);

	long long left = 0, right = 2147483647;

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


		if (solution(mid) % 2 == 0) {
			left = mid + 1;
		}
		else
		{
			ans = (int)mid;
			right = mid - 1;
		}
	}
	if (ans == -1)
	{
		printf("NOTHING");
	}
	else
	{
		printf("%d %d", ans, solution(ans) - solution(ans - 1));
	}
	return 0;
}

 

6. 결과