[백준/1637/Java] 날카로운 눈_간단 풀이

1. 문제 이해

• 총 n번 만큼
• A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수가 추가될 때
• 홀수개 존재하는 정수를 찾는 프로그램을 작성하시오.

2. 문제 해석

• 주어지는 수의 범위가 커서, 배열의 크기를 [Integer.MAX_VALUE]로 선언하면 메모리 초과 & 시간초과가 발생합니다.
• n개의 A, B, C에 대한 정보를 배열로 갖고 있으면 특정 수 이하의 수가 몇개 존재하는지도 O(n) 시간 내에 찾을 수 있습니다.

int count = 0;
for(int i = 0; i < n; i++) {
	if(특정 수 < A[i] || C[i] < 특정 수) 
    	continue;
    else {//Math.min을 사용하는 이유 : 특정 수가 C[i]보다 작을 경우를 고려하기 위함
	    int k =(Math.min(C[i], 특정 수) - A[i])/B[i] + 1;
		count += k;
    }
}
return count;

• 따라서, 파라메트릭 서치를 사용합니다.
  • mid 이하의 수가 홀수 개 존재한다 -> mid보다 작은 수 중 홀수개 만큼 존재하는 수가 있다.
  • mid 이하의 수가 짝수 개 존재한다 -> mid보다 큰 수 중 홀수개 만큼 존재하는 수가 있다.

3. 코드

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

import static java.lang.Integer.*;
import static java.lang.System.in;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(in));
    static int n;
    static int[] A, B, C;

    public static void main(String[] args) throws IOException {
        n = st(br.readLine());

        init();

        long left = 0L;
        long right = Integer.MAX_VALUE + 1L;
        long mid;

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

            int belowMid = countBelowMid(mid);

            if(belowMid % 2 == 0) {
                left = mid+1;
            } else {
                right = mid;
            }

        }

        System.out.println(left == Integer.MAX_VALUE+1L ? "NOTHING" : String.format("%d %d", left, count(left)));

    }

    public static int countBelowMid(long mid) {
        int belowMid = 0;
        for (int i = 0; i < n; i++) {
            if(mid < A[i] || C[i] < mid) {
                continue;
            }

            int count = (int) (Math.min(C[i], mid) - A[i])/B[i] + 1); //C[i]의 값이 int의 범위 내에 존재함으로, 타입 캐스팅으로 인해 문제가 발생할 일은 없음.
            belowMid += count;
        }

        return belowMid;
    }

    public static int count(long num) {
        int numCount = 0;
        for (int i = 0; i < n; i++) {
            if(C[i] < num || A[i] > num) {
                continue;
            }

            if((num-A[i]) % B[i] == 0) {
                numCount ++;
            }
        }

        return numCount;
    }

    private static void init() throws IOException {
        String[] line;
        int a, b, c;
        A = new int[n];
        B = new int[n];
        C = new int[n];

        for (int i = 0; i < n; i++) {
            line = br.readLine().split(" ");

            a = st(line[0]);
            c = st(line[1]);
            b = st(line[2]);

            A[i] = a;
            B[i] = b;
            C[i] = c;
        }
    }

    public static int st(String str) {
        return parseInt(str);
    }

}

4. 코드 해석

• countBelowMid() 메서드는 위에서 이미 설명을 마쳤습니다.

• 파라메트릭 서치 파트

  • right의 시작 값을 Integer.MAX_VALUE에 1을 더한 값으로 설정한 이유는, 그래야 문제에서 주어진 범위를 모두 탐색할 수 있기 때문입니다.
    이렇게 하지 않고 Integer.MAX_VALUE로 right의 시작 값을 설정하면 다음 반례를 통과할 수 없습니다.

    반례: 2147483647 2147483647 1

  • 만약 nothing인 케이스면, left는 계속 증가하다가 결국 right과 같은 값이 되어 while 루프가 끝이 납니다.

  • 정답이 있는 케이스일 경우 while 루프가 끝났을 때 left = right = 정답이 됩니다.

• 정답 수의 개수를 세기 위한 count() 메서드의 경우,
  다른 분들의 코드를 참고해 보니 countBelowMid(mid) - countBelowMid(mid-1)으로 코드 작성을 최소화 하는 방법도 있었습니다.