백준 1637 날카로운 눈 자바

 

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

1637번: 날카로운 눈

 

정수더미 속에서 홀수 개 존재하는 정수를 찾으면 되는 문제입니다.

 

예제 입력을 보면 A C B 가 차례로

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

 

정수더미는 위와 같이 있습니다.

 

이 정수더미를 1 이하의 수의 개수, 2 이하의 수의 개수, ..... 10 이하의 개수를 나타내보겠습니다.

1    2    3    4    5    6   7   8   9   10

2   4    6    9    11   13  15  17  19  21

규칙이 좀 보이시나요???

 

중간에 홀수 개의 정수가 있으면 그 이후에는 모두 홀수 개가 나오게 됩니다.

그렇다면 이진탐색 파라메트릭 서치를 이용할 수 있게 됩니다.

이진탐색으로 홀수인 것 중에 가장 왼쪽인 것을 찾아주면 홀 수 개의 정수를 찾을 수 있게 됩니다.

 

파라메트릭 서치를 모르신다면 한 번 검색하셔서 익히신 뒤 문제를 다시 봐보시는 것을 추천드립니다.

 

    public static int[][] arr;

    public static boolean check(long num){

        long total = 0;

        for(int i = 0; i < arr.length; i++){

            long n = Math.min(arr[i][1], num);
            if(n >= arr[i][0]) {
                total += 1 + (n - arr[i][0]) / arr[i][2];

            }
        }

        return total % 2 == 1;

    }

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        arr = new int[N][3];

        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(),  " ");

            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            arr[i][2] = Integer.parseInt(st.nextToken());
        }

        long s = 1;
        long e = Integer.MAX_VALUE;
        long ans = 0;


        while(s <= e){
            long mid = (s + e) / 2;

            if(check(mid)){
                ans = mid;
                e = mid - 1;
            }else{
                s = mid + 1;
            }

        }

        int count = 0;

        for(int i = 0; i < arr.length; i++){

            if(ans <= arr[i][1] && ans >= arr[i][0]){
                if((ans - arr[i][0]) % arr[i][2] == 0){
                    count++;
                }
            }

        }


        if(count % 2 == 0){
            System.out.println("NOTHING");
            return;
        }

        System.out.println(ans + " " + count);