[백준] 1637 날카로운 눈

문제소개

---

1637날카로운 눈은 이분 탐색 문제입니다. 문제 분류가 DFS로 분류되어 있어서 어떻게 하면 DFS로 풀 수 있을까를 생각하느라 조금 오래 걸렸습니다. (DFS로 풀진 못했습니다.)

 

문제의 입력값이 20억 이므로 O(N)이 아닌 O(logN)의 알고리즘을 생각해야 하며 O(logN)에 어울리는 탐색 방법으로 이분 탐색을 생각할 수 있습니다. log2(2,000,000,000)  ≒ 602,059,991

그러면 어떻게 생각해야 '1637날카로운 눈' 문제에 이분 탐색을 적용할 수 있을까요? 

그 해답의 포인트는 홀수 개수를 가진 특정 정수는 하나라는 점입니다.

 

문제풀이

 

---

4 1 10 1 4 4 1 1 5 1 6 10 1

 

 

 

 

다음과 같은 입력값을 아래와 같이 표로 정리했습니다.

 

	1	2	3	4	5	6	7	8	9	10
				4
	1	2	3	4	5
						6	7	8	9	10
개수	2	2	2	3	2	2	2	2	2	2
누적합계	2	4	6	9	11	13	15	17	19	21

 

 

 

표를 통해 금방 눈치를 채셨을 것 같습니다.

주어진 문제에서 홀수 개수를 가진 특정 정수가 하나이기 때문에 

 

짝수 + 짝수 ⇒ 짝수

홀수 + 짝수 ⇒ 홀수

 

의 규칙을 적용하면 정답을 기준으로 왼쪽은 짝수,

오른쪽은 홀수의 규칙을 갖게 됩니다. 

그러므로 이분 탐색을 통해 정답을 찾을 수 있는 문제로 정리 됩니다.

 

 

 

 

 

i	1	2	3	4	5	6	7	8	9	10
				4
	1	2	3	4	5
						6	7	8	9	10
개수	2	2	2	3	2	2	2	2	2	2
누적합계	2	4	6	9	?

 

예를 들어 위 입력값으로 이분탐색을 진행해보겠습니다. 

left = 1, right = 10, mid = (1 + 10)/2 = 5

각 정수 더미의 시작 값 A[i] 보다 5가 크거나 같다면

5까지 각 정수의 빈도수 누적 합 : (( min(5,C[i]) - A[i] ) / B[i] ) + 1 이므로

누적합계는 11입니다. 

누적합이 홀수 이므로 right = mid로 범위를 줄여나가며 

이러한 과정을 반복하면 아래와 같습니다.

 

left=1 right=10 mid=5일때
0	5
1	1
2	5
3	0
누적합계	11

    

 

left=1 right=5 mid=3일때
0	3
1	3
2	0
3	0
누적합계	6

 

left=4 right=5 mid=4일때
0	4
1	1
2	4
3	0
누적합계	9

 

left =4, right = 4 이므로 while (left<right) 문이 종료됩니다.

정답은 left인 4가되며

4의 빈도수는 누적합계(4) - 누적합계(3)으로 해결할 수 있습니다.

 

---

소스보기