Q. 1637 자바 : 날카로운 눈

Q. 1637 자바 : 날카로운 눈

 

문제 : boj.kr/1637

P4 난이도의 문제이다.

 

문제를 간단히 설명하자면 n개의 입력이 주어지고 입력마다 a, c, b가 주어진다.

각각의 입력에 대해 a, a + b, ... a+kb(a + kb <= c)인 숫자를 모두 하나의 정수 더미에 넣었을 때

특정한 정수 하나만 홀수개 존재한다면 그 정수와 몇개 존재하는지를 구하는 문제이다.

 

예를들어 아래와 같이 입력이 주어졌다면

4
1 10 1
4 4 1
1 5 1
6 10 1

첫 번째 입력은 1, 2, 3, 4, 5, 6, 7, 8, 9, 10의 정수 더미를

두 번째 입력은 4

세 번째는 1, 2, 3, 4, 5

네 번째는 6, 7, 8, 9, 10을 의미한다.

 

이를 모두 합치면 정수 4가 3개 존재하므로 4 3을 출력하면 된다.

---

먼저 완전 탐색 방식으로 푼다고 가정하면 아래와 같이 풀었을 것 같다.

1. 위 예시와 마찬가지로 모든 입력들에 대해 정수 더미를 만든다.

2. 정수 더미를 정렬한다.

3. 정수 더미를 하나씩 세며 홀수 개 있는 정수를 계산한다.

 

이렇게 푼다면 정수 a, b, c의 범위가 약 21억 이므로 1번 과정만 약 21억번의 계산이 필요하다.

시간제한은 2초이므로 이 방법은 불가능해 보였다.

그래서 완전 탐색이 아닌 다른 방법을 생각해야 한다.

---

먼저 입력의 수 n이 20,000이므로 O(n) 또는 O(n logn) 정도면 풀 수 있을 것 같다.

그리고 이 정수 더미들의 집합은 이분 탐색의 특징을 보이는데, 정렬된 정수 더미에서 특정 정수 x 이하인 숫자들을 셌을 때 짝수개인지 홀수개인지만 판단한다면 구간을 줄이는 방식으로 풀 수 있다.

 

즉 정수 x를 정하고  정렬된 정수 더미에서 x이하인 숫자들을 셌을 때 짝수개인지 홀수개인지만 판단하는 결정 문제로 바꿀 수 있다.

이 경우 정수 x는 약21억이고 n개의 정수 더미가 존재하므로 O(n logx)의 시간복잡도로 풀 수 있다.

log x는 약 30정도이므로 O(n)으로 봐도 될 것 같다.

 

아래와 같은 방식으로 풀었다.

1. 정수 x에 대해 이분탐색을 한다. - O(log x)

2. 결정 문제는 x 이하인 정수 더미가 홀수개인가? 이다. -  O(n)

2-1. 이 때 x 이하인 정수 더미의 숫자가 int 범위를 초과할 수 있으므로 주의해야 한다. 

 

import java.io.*;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static int[][] inputNum;
    static int n;

    static void input() throws IOException {
        n = Integer.parseInt(br.readLine());

        inputNum = new int[n][3];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                inputNum[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

    static long count(int a, int c, int b, long mid) {
        if (mid < a) return 0;
        int res = 1;

        if (c < mid) res += (c - a) / b;
        else res += (mid - a) / b;

        return res;
    }

    static boolean determination(long mid) {
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += count(inputNum[i][0], inputNum[i][1], inputNum[i][2], mid);
        }
        return sum % 2 == 1;
    }

    static void pro() {
        long left = 1, right = Integer.MAX_VALUE, ans = 0;

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

            if (determination(mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        int sum = 0;
        for (int i = 0; i < n; i++) {
            int a = inputNum[i][0];
            int c = inputNum[i][1];
            int b = inputNum[i][2];

            long ansMinA = ans - a;
            if (0 <= ansMinA && ans <= c && (ansMinA % b == 0)) sum++;
        }

        if (sum % 2 == 1) {
            sb.append(ans).append(' ').append(sum);
        } else {
            sb.append("NOTHING");
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}