[JAVA] 백준 1637 : 날카로운 눈

문제

1637번: 날카로운 눈

 

해결방법

개인적으로 이해하는데에 많은 시간을 소모해서

다음에 이와 같은 문제를 봤을 때 이해하는 속도를 높히고자 글을 작성해둔다.

 

이 문제는 정수더미에 수 많은 숫자들이 들어있고, 그 중에서 하나의 숫자만 홀수개 존재하는데

그래서 정수더미에 있는 수 중 홀수개 존재하는 숫자가 무엇인지 또 몇 개 들어있는지를 출력하는 문제이다.

 

예제 1의 입력을 보면 1 10 1 과 같이 3개의 숫자가 주어지는데 의미는 1부터 1씩 커지는 숫자가 10까지 존재한다는 의미로써 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 을 정수더미에 추가한다는 말이다.

 

두번째 입력을 보면 4 4 1 인데 4부터 1씩 커지는 숫자가 4까지 존재한다는 의미이므로 4 하나만 추가되고,

1 5 1 과 같은 경우 1부터 1씩 커지는 숫자가 5까지 존재, 1, 2, 3, 4, 5 가 정수더미에 추가되는 형식이다.

 

그래서 이 모든 수를 배열에 집어넣어 갯수를 확인 할 수 있지만, 범위가 상당히 넓어 시간이 초과된다.

그래서 이분탐색을 사용하는데 이분탐색에는 해당하는 값까지 존재하는 숫자들의 갯수를 사용한다.

 

즉, mid값이 3라면 1부터 3까지 존재하는 숫자가 몇 개인지를 구하는 것으로써 1 1 1 2 2 3 3 4 4 5 5 가 존재한다고 하면 1 1 1 2 2 3 3 이 값에 해당되므로 7개가 존재한다라는 것에서 부터 풀이가 시작된다.

 

그래서 해당 값까지의 숫자 갯수의 총합 을 구하는 식은 이와 같다.

for (int i = 0; i < N; i++) {

    if (mid >= A[i]) Math.min(mid, C[i]) - A[i]) / B[i] + 1

}

해석하면 최솟값이 mid값보다 작을 때 (크면 해당하는 숫자가 존재하지 않기 때문)

해당 mid 값까지 (최대값이 mid보다 작으면 그 값까지) 에서 최솟값을 뺀 숫자에서 공차를 나눠주면 된다.

그리고 시작값을 1 더해준다.

 

A B C가 각각 1 1 10 이고 mid가 5일 때를 예로 들면 5까지의 숫자 갯수의 총합은

mid가 C보다 작으므로 5에서 최소값인 A 즉, 1을 빼서 구간의 길이를 구한다.

그 구간의 길이에 공차인 B가 몇 번 존재하는지를 확인하기 위해 나누어주고 그러면 4 / 1이 되어 4번 

1에서 2로 커질 때 1번, 2에서 3, 3에서 4, 4에서 5로 커지면서 4개의 수가 존재할 수 있고, 시작값을 하나 더해주어 총 5개의 숫자가 이 예시에서 존재함을 알 수 있다.

 

이분 탐색은 해당하는 숫자까지의 갯수의 총합이 홀수이면 그 값들 안에 홀수인 정수가 포함되어있다는 뜻이므로

이를 통해 left와 right값을 조절하며 해당 값을 찾아낸다.

 

참조한 블로그 : https://hoho325.tistory.com/236

 

코드

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

public class Bj_1637 {
	static int N;
	static int[] A, B, C;
	
	// 값의 범위가 int를 넘어가서 Long을 사용했다.
	static long min = Long.MAX_VALUE;
	static long max = Long.MIN_VALUE;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		
		A = new int[N];
		B = new int[N];
		C = new int[N];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			A[i] = Integer.parseInt(st.nextToken());
			C[i] = Integer.parseInt(st.nextToken());
			B[i] = Integer.parseInt(st.nextToken());
			
			min = Math.min(min, A[i]);
			max = Math.max(max, C[i]);
		}
		max++;
		bs();
	}
	
	static void bs() {
		long left = min;
		long right = max;
		
		while (left < right) {
			long mid = (left + right) / 2;
			
			long sum = getSum(mid);
			
			// mid까지의 숫자갯수의 총합이 짝수면 조사하지 않은 범위에
			// 홀수인 정수가 존재한다는 의미이므로 left = mid + 1
			if (sum % 2 == 0) {
				left = mid + 1;
				
			// mid까지의 숫자갯수의 총합이 홀수면 해당 영역에 
			// 홀수인 정수가 존재한다는 의미이므로 right = mid;
			} else {
				right = mid;
			}
		}
		
		// 탐색을 마쳤을 때 left가 max라면 홀수인 값이 없다는 뜻
		if (left == max) System.out.println("NOTHING");
		
		// 아니라면 해당하는 숫자를 구하기 위해 아래와 같은 식을 사용
		else {
			long num = getSum(left) - getSum(left - 1);
			System.out.println(left + " " + num);
		}
	}
	
	static long getSum(long mid) {
		long sum = 0;
		for (int i = 0; i < N; i++) {
			if (mid >= A[i]) sum += (Math.min(mid, C[i]) - A[i]) / B[i] + 1;
		}
		return sum;
	}
}