백준 1637 JAVA : 날카로운 눈

문제

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

1637번: 날카로운 눈

 

풀이 예상

아무리 이분탐색 인걸 알아도.. 생각한 방법들은 시간초과 날 게 뻔하고.. 고민을 너무 오래해서 결국 답을 보고 풀었다.

 

이 문제에서 이분탐색의 범위를 나누는 조건은 mid 값 이하인 수를 전부세서 count한 개수가 홀수인지 짝수인지 판별하는 것이다.

 

예제를 예시로 들면, 아래처럼 개수가 카운트 된다.

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

 

위 표를 누적합 처리(이전 값 더하기)를 해보면, 아래와 같이 되는데 홀수개인 값(4) 를 기준으로 왼쪽은 전부 짝수, 오른쪽은 전부 홀수인 것을 볼 수 있다.

1	2	3	4	5	6	7	8	9	10
2	4	6	9	11	13	15	17	19	21

 

이 점을 활용하여 이분탐색 코드를 작성하고, 그 안에서 홀수개인지 짝수개인지 체크하는 로직은

A : 1, B : 10, C : 1 이고 mid  가 5인 경우

(B와 mid중 작은 값(끝점) - A(시작점) + 1) / C 라는 식으로 구할 수 있다. (나머지가 있을 경우 +1)

long count = 0;
for (int i = 0; i < N; i++) {
	if(arr[i][0] <= mid){
		//mid가 시작점보다 크거나 같을때만
		long answer = Math.min(mid, arr[i][1]) - arr[i][0] +1;
		if(answer % arr[i][2] == 0) {
			count += answer / arr[i][2];
		}else {
			count += answer / arr[i][2] + 1;
		}
	}
}

 

 

마지막으로, 홀수 개인 지점을 찾았을 때, 홀수개인지 마지막으로 체크하는 로직은

A : 1, B : 10, C : 2 이고 mid  가 5인 경우

mid가 A와 B 사이에 있고, mid - 시작점(A) 을 C로 나눴을 때 나머지가 0이면 해당 mid수가 들어있다고 식을 세울 수 있다.

long count = 0;
for (int i = 0; i < N; i++) {
	if(arr[i][0]<= point && point<= arr[i][1] && (point-arr[i][0])%arr[i][2] == 0) {
		count++;
	}
}

 

풀이방법 (접근 방법 & 시간복잡도)

 

시간복잡도 => O(N * log M)  - M: 2_147_483_647

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {
    static int N;
    static long[][] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new long[N][3];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][0] = Long.parseLong(st.nextToken()); //A
            arr[i][1] = Long.parseLong(st.nextToken()); //B
            arr[i][2] = Long.parseLong(st.nextToken()); //C
        }

        long start = 1;
        long end = 2_147_483_647;

        while(start <= end) {
            long mid = (start+end)/2;
            if(checkOdd(mid)) {
                //홀수면 범위 아래로
                end = mid-1;
            }else {
                start = mid+1;
            }
        }
        countResult(start);


    }

    private static void countResult(long point) {
        long count = 0;
        for (int i = 0; i < N; i++) {
            if(arr[i][0]<= point && point<= arr[i][1] && (point-arr[i][0])%arr[i][2] == 0) {
                count++;
            }
        }

        if(count%2 == 1) {
            System.out.println(point+" "+count);
        }else {
            System.out.println("NOTHING");
        }

    }

    private static boolean checkOdd(long mid) {
        //mid보다 같거나 작은 수 카운트해서 홀수개인지 확인
        long count = 0;
        for (int i = 0; i < N; i++) {
            if(arr[i][0] <= mid){
                //mid가 시작점보다 크거나 같을때만
                long answer = Math.min(mid, arr[i][1]) - arr[i][0] +1;

                if(answer % arr[i][2] == 0) {
                    count += answer / arr[i][2];
                }else {
                    count += answer / arr[i][2] + 1;
                }
            }

        }
        return count % 2 == 1;
    }
}

결과