Ethan Hur's blog

백준 온라인 저지 #1637 날카로운 눈

2017-10-18

오랜만에 PS 문제를 풀었다. 해당 문제는 여기에서 확인할 수 있다.

갓갓류(rhs0266)의 추천으로 접하게 된 문제이다.

Parametric Search 를 이용해서 푸는 문제였는데, 다른 문제와는 다르게 어떤 조건으로 Binary Search 를 할 지가 키포인트였다.

사실 코드를 올리기 심히 부끄러우나, 그래도 로그삼아 올린다.

맞은 사람 중에서 등수는 3등인데 왜이런지 모르겠다 ㅋㅋㅋ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<stdio.h>
#define MAX 20001
#define INT_MAX 2147483647
int a[MAX], b[MAX], k[MAX], n;
int getNum(int i, int limit) {
if (limit < a[i]) return 0;
int bb = b[i] > limit ? limit : b[i];
int x = (bb - a[i]) / k[i] + 1;
return x;
}
long long int getNums(int limit) {
long long int sum = 0;
for (int i = 0; i < n; i++) {
sum += getNum(i, limit);
}
return sum;
}
void p_search(long long int min, long long int max) {
if (min >= max) {
if (min == INT_MAX)printf("NOTHING\n");
else printf("%lld %lld", min, getNums(min) - getNums(min - 1));
return;
}
long long int med = (min + max) / 2;
if (getNums(med) % 2 == 1) {
p_search(min, med);
}
else {
p_search(med + 1, max);
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d %d %d", &a[i], &b[i], &k[i]);
}
p_search(0, INT_MAX);
return 0;
}

첫 제출은 Wrong Answer 가 떴는데, 이는 med 값을 구할 때 med 를 int 로 선언하였는데

min + max 가 INT-MAX/2 + INT-MAX 가 될 수도 있어 오버플로우가 발생하였기 때문이다.

나처럼 long long int 로 바꿔도 되고, 그게 싫다면

1
int med = min + (max - min) / 2;

이런 식으로 계산하면 int 범위 내에서 계산할 수 있을 것이다.

Tags: PS