[백준] 이분탐색 - 1637번: 날카로운 눈 (Java)

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

1637번: 날카로운 눈

문제

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 원숭이는 좀 특이한 원숭이였다. 어떤 것도 꿰뚫어볼 수 있는 날카로운 눈을 가진 기이한 원숭이였다. 부드러운 눈을 가진 멍멍이는 언제나 날카로운 눈을 가진 원숭이를 부러워했지만 한편으로는 매우 질투했다.

어느 날 멍멍이는 원숭이의 날카로운 눈이 너무 샘나서 원숭이를 직접 패고 싶었지만 날카로운 눈으로 찌를까봐 무서워서 때리지는 못하고 대신, 원숭이에게 문제 하나를 던져주었다. 그 문제는 다음과 같다.

정수가 여러 개 모여 있는 정수더미가 있다. 그 안에 어떤 특정한 정수 하나만 홀수개 존재하고 나머지 정수는 모두 짝수개 존재한다. 정수더미 속에서 날카로운 눈을 이용해 홀수개 존재하는 정수를 찾아야 하는 문제이다.

근데 멍멍이가 문제를 전달해 주려다가 생각해보니 정수더미 안에 정수가 적게 있으면 문제가 너무 쉬워지게 되는 것이다. 그래서 정수더미안에 정수를 무지막지하게 많이 넣기로 했다. 정수더미가 주어졌을 때, 그 안에 홀수개 존재하는 정수를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 입력의 개수 N이 주어진다. N은 1이상 20,000이하인 수이다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수들이 정수더미 안에 있다는 것을 나타낸다. A, B, C는 1보다 크거나 같고 2,147,483,647보다 작거나 같은 정수이다. 정수더미는 N개의 입력이 나타내는 정수들을 모두 포함한다.

출력

첫째 줄에 정수 두 개를 출력하는데, 첫 번째는 홀수개 존재하는 정수를 출력하고, 두 번째는 그 정수가 몇 개 들어있는지 출력한다. 만약 홀수개 존재하는 정수가 없다면 NOTHING을 출력한다.

어려웠다...

입력부터 A, C, B 순서로 입력받지만, A, A + B, A + 2B + ··· + A + kB <= C 이다.

1 10 1이 입력되었다면, 주머니 안에는 1, 2, 3, 4, 5, 6, 7, 8, 9, 10이 들어있는 셈이다.

이러한 주머니에서 홀수개가 들어있는 정수를 찾아야하는 문제이다.

누적합을 이용해서 풀었다. 참고로 여기서 누적합은 자연수 K 까지 수의 개수이다.

1. L과 R을 주머니 안에 있는 최솟값 / 최댓값으로 설정하고 시작한다.
2. MID 를 구하고 MID 까지의 누적합을 구한다
   1. 누적합 계산은 sum += Math.min(MID, C[i] - A[i]) / B[i] + 1
   2. min 메소드를 사용하는 이유는 kB이외의 다른 값이 포함될 수 있기 때문이다.
   3. Math.min(MID, C[i] - A[i]) / B[i] 을 통해 k를 구하고 +1 을 해주어서 A를 더해준다
3. 누적합이 홀수이면 MIN ~ MAX 사이에 원하는 값이 존재하므로 R을 감소시키고 짝수이면 원하는 값이 MID 보다 오른쪽에 있으므로 L을 증가시킨다.
4. while문을 탈출하여
   1. answer == 0 이면 NOTHING
   2. 결과값의 개수는 (결과값의 누적합) - (결과값 - 1의 누적합) 이다.