백준#1637 날카로운 눈 (java)

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        new Sol();
    }
}
class Sol{
    int N;
    private final Buf buf = new Buf();
    List<ABC> input = new ArrayList<>();
    public Sol(){
        N = buf.readInt();
        for (int i = 0; i<N; i++){
            input.add(new ABC(buf.readInt(), buf.readInt(), buf.readInt()));
        }
        if (!isOddNum(Integer.MAX_VALUE)){
            System.out.println("NOTHING");
            return;
        }

        long right = Integer.MAX_VALUE;
        long left = 0;
        while(left<right){
            long mid = (right+left)/2;
            if (isOddNum(mid)){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        System.out.println(left + " "+ num(left));
    }
    public boolean isOddNum(long mid){
        long tmp = 0;
        for (int i = 0;i<N; i++){
            ABC abc = input.get(i);
            if (mid<abc.a)continue;
            long K = Math.min(mid, abc.c);
            tmp+=(K-abc.a)/abc.b+1;
        }
        return tmp%2==1;
    }

    public int num(long a){
        int num = 0;
        for (int i =0;i<N;i++){
            ABC abc = input.get(i);
            if (abc.c<a||a<abc.a)continue;
            if ((a-abc.a)%abc.b==0)num++;
        }
        return num;
    }
}
class ABC{
    int a, c, b;

    public ABC(int a, int c, int b) {
        this.a = a;
        this.b = b;
        this.c = c;
    }

    public int getA() {
        return a;
    }

    public int getB() {
        return b;
    }

    public int getC() {
        return c;
    }
}
class Buf{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;

    public String read(){
        while(st==null||!st.hasMoreElements()){
            try{
                st = new StringTokenizer(br.readLine());
            }catch(IOException e){
                return null;
            }
        }
        return st.nextToken();
    }
    public Integer readInt(){
        return Integer.parseInt(read());
    }

    public Long readLong(){
        return Long.parseLong(read());
    }
}

 

풀이

해당 문제에서 단순히 임의의 K까지의 각 정수 개수를 찾는다면 21억 번이 훨씬 넘을 수 있다. 때문에 정수의 개수가 아닌 N을 기준으로 해야 시간 초과를 피할 수 있다. 입력이 특이한데 다음과 같은 의미를 가진다.

예)

4
1 10 1		#1 2 3 4 5 6 7 8 9 10
4 4 1		#4
1 5 1		#1 2 3 4 5
6 10 1		#6 7 8 9 10

 

즉 N에 임의의 n번째 규칙은 A+kB <= C와 같다. 이때 C 대신 K(A<=K, 임의의 정수)를 넣으면 A+k`B <= K, 그러니까 k` 이 나올 수 있는 개수가 n번째 규칙에서 K보다 작은 정수들의 개수를 알 수 있다. 즉 N 번 반복하면 K 보다 작은 정수의 총개수를 알 수 있다.

 

또한 홀수개의 정수가 단 하나만 있다면 전체 정수의 개수 또한 홀수이다. 즉 다음과 같이 표현된다.

이 부분은 매개변수 이진 탐색이면 풀 수 있다.

 

구현

 

public boolean isOddNum(long mid){
    long tmp = 0;
    for (int i = 0;i<N; i++){
        ABC abc = input.get(i);
        if (mid<abc.a)continue;
        long K = Math.min(mid, abc.c);
        tmp+=(K-abc.a)/abc.b+1;
    }
    return tmp%2==1;
}

탐색 조건이다. 이때 k`는 0이 될 수 있으므로 +1 을 해준다. K가 C보다 커도 최대 C까지만 있기 때문에 둘 중 작은 값이 곧 K가 된다. 따라서 모두 더한 후 짝수인지 홀수인지만 확인해 주면 된다.

if (!isOddNum(Integer.MAX_VALUE)){
    System.out.println("NOTHING");
    return;
}

특별 요구사항에 없는 경우가 있으므로 32비트 정수형의 최대 값 (C의 최대값) 을 넣어서 홀수가 없다면 바로 NOTHING을 출력하고 종료시켜 버린다.