백준 1637 java - 날카로운 눈(이진탐색, 누적합, 정수론/feat.생애첫플레 1솔)

문제, 입출력, 테스트케이스

해당 문제는 결국 구선생님의 힘을 빌어서 풀게 되었으나 그래도 나만의 방식으로 풀어냈다.

이진탐색 + 누적합 + 정수론의 조합이기 때문에 좀 까다로웠다. 정수론이라고 치기에 애매하긴 하지만...

생애 첫 플레티넘 문제 1솔을 했다!!

 

<문제 접근/풀이과정>
1. 이진탐색(매개변수탐색)은 결국 순서대로 탐색하기 + 단절점 찾기가 핵심이다.
2. 일단 탐색할 값을 뭐로 할 지 정해야하는데 입력값중 압도적으로 큰 21XXXXX이 있어서 탐색값은 1 <= X <= 21xxxx으로 정했다.
3. 여기서부터가 문제다. 문제에서 힌트를 주었는데 홀수인 게 한 개 또는 없거나라는 점
짝수 + 짝수 = 짝수
홀수 + 홀수 = 짝수
짝수 + 홀수 = 홀수
라는 점을 이용하면 특정 숫자의 누적합 기준 홀수라면 => 그 특정 숫자 이하의 숫자 중에 홀수 개인 수가 존재한다는 것이고 짝수라면 그 특정 숫자 초과의 값에 홀수가 존재하거나 홀수 숫자가 해당 배열에 없다는 뜻이다.
4. 의미없는 최적화 일 수 있지만 본인은 NOTHING인 경우를 제일 먼저 떠올렸다. 
=> (C - A) / B + 1 의 누적합이 짝수인 경우에는 무조건 NOTHING일 수밖에 없다 왜냐하면 홀수개인게 하나고 나머지가 짝수이므로 누적합이 짝수인 경우에는 무조건 홀수가 없다는 뜻이기 때문이다.
5. 정답을 출력할 때는 홀수 개가 존재하는 특정 숫자에다가 그 숫자의 갯수를 출력해야하는데 그 숫자의 갯수는 누적합(특정숫자) - 누적합(특정숫자-1)하면 구할 수 있다.

package 이진탐색;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Boj_1637 {
	static long A[], B[], C[];
	static int N;
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 1 2 3 4 5 6 7 8 9 10
		// 4
		// 1 2 3 4 5
		// 6 7 8 9 10
		// 홀수 중 1 ~ 19999개가 존재할 수 있어
		//
		// 1 2 3 4 5 6 7 8 9 10
		// 2 2 2 3 2 2 2 2 2 2

		// target = A*k + B <= C가 되니?

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		int total = 0;
		A = new long[N];
		B = new long[N];
		C = new long[N];
		long max = -1;
		long min = Integer.MAX_VALUE+200000;
		for (int i = 0; i < N; i++) {
			String temp[] = br.readLine().split(" ");

			A[i] = Integer.parseInt(temp[0]);
			B[i] = Integer.parseInt(temp[2]);
			C[i] = Integer.parseInt(temp[1]);
			max = Math.max(max, C[i]);
			min = Math.min(min, A[i]);
			
			total += ((C[i] - A[i]) / B[i] + 1) % 2;
		}

		if ((total & 1) == 1) {
			long s = min;
			long e = max;
			long answer = 0;
			while (s <= e) {
				long mid = (s + e) >> 1;
				
				if (check(mid)) {
					answer = mid;
					e = mid -1;
				} else {
					s = mid + 1;
				}
			}
			System.out.println(answer +" " + (getCnt(answer)- getCnt(answer-1)));
		} else { // 홀수 + 짝수 = 홀수이므로 전체 경우의 수 다 더했을 때 짝수가 나온다는 건 홀수개 존재하는 정수가 없다는 뜻
			System.out.println("NOTHING");
		}
	}

	private static long getCnt(long answer) {
		long total = 0;
		
		for (int i = 0; i < N; i++) {
			if(A[i] <= answer) {
				total += (Math.min(answer, C[i]) - A[i]) / B[i] + 1; 
			}
		}
		return total;
	}

	private static boolean check(long mid) {
		long total = 0;
		for (int i = 0; i < N; i++) {
			if(A[i] <= mid) {
				total += (Math.min(mid, C[i]) - A[i]) / B[i] + 1; 
			}
		}
		return (total & 1) == 1;
	}
}

생애 첫 플레티넘 문제 1Solve이다. 행복하다.