[백준] 1637 날카로운 눈 - Java

 

 

 

입력으로 들어온 수 중 홀수 개 존재하는 수는 하나 뿐이다.

모든 경우를 싹다 찾아보며 문제를 풀려고 하면 당연히 시간 초과가 날 테니까.. 다른 방법을 생각해보자.

 

특정 정수 하나만 홀수 개 존재하고, 나머지 수는 모두 짝수개를 가진다.. 

 

홀수 개 존재하는 정수보다 큰 정수에 대해서 개수의 합을 구하면 홀수 개가 나오고, 홀수 개 존재하는 정수보다 작은 정수에 대해서 개수의 합을 구하면 짝수 개가 나온다.

 

이 부분에 집중해서 매개 변수 탐색을 수행하자.

 

 

 

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

public class Main {

	static int N;
	static int[][] input;
	
	//static long ans_num;

	static int max = Integer.MIN_VALUE;	

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		N = Integer.parseInt(br.readLine());		
		
		input = new int[N][3];

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

		
	}

	static long count(long A, long C, long B, long Upper){
		if(Upper < A){
			return 0;
		}

		if(C < Upper){
			return ((C - A) / B) + 1;
		}else{
			return ((Upper - A) / B) + 1;
		}
	}

	static boolean odd_check(long p){
		long sum = 0;
		for(int i=0; i<N; i++){
			sum = sum + count(input[i][0], input[i][1], input[i][2], p);
		}

		if(sum % 2 == 1){
			//ans_num = sum;
			return true;
		}else{
			return false;
		}
	}

	static void BinarySearch(){
		long L = 1;
		long R = Integer.MAX_VALUE;
		long ans = 0;

		while(L <= R){
			long mid = ( L + R ) / 2;
			if(odd_check(mid)){
				ans = mid;
				R = mid - 1;
			}else{
				L = mid + 1;
			}
		}

		long ans_cnt = 0;


		if(ans == 0){
			System.out.println("NOTHING");			
		}else{						
			for (int i = 0; i < N; i++) {
				if (input[i][0] <= ans && ans <= input[i][1] && (ans - input[i][0]) % input[i][2] == 0) {
						ans_cnt++;
				}
		}
		System.out.println(ans + " " + ans_cnt);
		}
	}

}