[BOJ] 3090번 - 차이를 최소로

 

 

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

 

그리디 + 파라메트릭 서치를 사용하는 문제이다.

문제를 풀고 블로그 풀이들을 보는데 내가 푼 방법이랑 많이 달랐고, 하나같이 이걸 어떻게 생각함(...) 식의 풀이여서 글을 쓰게 되었다.

(시험 기간에 공부하기 싫어서 쓴 것도 있다.)

---

 

 

우선 보자마자 파라메트릭 서치를 쓰면 좋을 것 같다는 생각이 들었다.

인접한 원소 간 차이의 최댓값을 한 번에 최소화하는 것보다, 인접한 원소 간 차이가 어떤 $d$ 이하가 되도록 연산을 수행할 수 있는지 판별하는 게 더 쉬워 보였기 때문이다.

 

여기서 한 가지 관찰을 할 수 있는데, 배열 $A$의 최소 원소를 $m$이라 두면, 연산을 최적으로 수행하고 얻은 결과 배열의 모든 원소는 $m$보다 크거나 같다.

이는 배열의 각 원소에 1을 빼는 연산밖에 할 수 없기 때문이고, 생각해보면 자명하다. 원소에 1을 더하는 연산까지 할 수 있었다면 문제가 매우 어려워질 것 같다.

이것을 조금 발전시키면, 최솟값 $m$에 대해서 $m$과 인접한 원소들은 $m+d$ 이하여야 한다는 것을 알 수 있다. 그렇게 최솟값을 계속 뽑음으로서 결정 함수를 만들 수 있지 않을까? 하는 생각이 든다. 지금까지 한 관찰을 이용해서 결정 함수를 설계해보자.

 

 

모든 원소를 set에 넣고, set이 빌 때까지 아래 연산을 수행한다:

 

현재 set의 최소 원소를 $m$이라 두면, 수열 $A$ 상에서 $m$과 인접한 두 원소의 값을 $m+d$ 이하가 되도록 재설정한다.

변경한 원소들의 값 또한 set에서 갱신시켜주고, set에서 $m$을 제거한다.

 

Set에는 수열의 값 뿐만 아니라 값에 해당하는 인덱스 정보 또한 존재해야 하므로, pair<int, int> 자료형으로 set을 선언했다.

위 과정이 끝나면 지금까지 재설정하여 바뀐 값의 총량이 $T$보다 작거나 같은지 판별해서 true/false를 리턴한다.

예를 들어, 수열 $A$가 [1, 3, 6, 2]이고 $d=1$일 때, 각 iteration마다 바뀌는 값을 살펴보면 다음과 같다.

(수열 A의 값이 갱신됨과 동시에 set 또한 갱신되는 것에 유의하자.)

Set	m	A	변화량 누적 합
[ [1, 1], [2, 4], [3, 2], [6, 3] ]	1	[1, 3, 6, 2]	0
[ [2, 2], [2, 4], [6, 3] ]	2	[1, 2, 6, 2]	1
[ [2, 4], [3, 3] ]	2	[1, 2, 3, 2]	4
[ [3, 3] ]	3	[1, 2, 3, 2]	4
[ ]	-	[1, 2, 3, 2]	4

 

따라서, $A = [1, 3, 6, 2]$일 때 인접한 원소의 차이가 1 이하이도록 만들어 줄 때 필요한 최소 연산 수행 횟수는 4번이다.

 

 

위 알고리즘이 왜 올바른지는 직관적으로 증명할 수 있다.

현재 배열의 최솟값이 $m$이고, $a_i = m$이라 하자. 그러면 $a_{i-1} \le a_i + d$, $a_{i+1} \le a_i + d$가 당연하게 성립해야 한다.

이미 $a_{i+1} \le a_i + d$인 상태라면 가만히 놔두면 되고, $a_{i+1} > a_i + d$라면 $a_{i+1}$을 일단 $a_i + d$로 맞추고 보는 것이 최적이다. $a_{i+1}$은 적어도 그것보단 크거나 같아야 하기 때문이다. $a_{i-1}$에 대해서도 똑같은 작업을 수행하면 된다.

 

그렇게 수정한 배열에서 다음 최솟값을 찾고, $m' = a_j$이라 두자. 역시 $a_{j-1}, a_{j+1}$은 $a_j + d$보다 작거나 같아야 하므로 이것을 만족시키도록 값을 설정해준다. 여기서 한 가지 중요한 점은, 우리는 오름차순으로 배열을 순회하고 있으므로, $a_j$보다 $a_{j+1}, a_{j-1}$이 더 작은데 이 차이가 $d$보다 큰 상황은 절대 일어나지 않는다. $a_j$보다 더 작은 값에 대해서는 이전 단계들에서 인접한 원소 간 차이가 $d$ 이하가 되도록 설정해주었기 때문이다.

 

그렇게 위 작업을 반복하면 변화량의 누적 합이 최소가 되도록 작업을 수행할 수 있다.

 

---

 

 

여기서 한 가지 문제점은... 이대로 구현하면 시간 초과를 받는다!

시간복잡도를 분석해보면 $O(N\log{N} \cdot \log{1e9})$ 정도인데, 1억을 넘지 않아 돌아갈 것도 같지만 set의 상수는 생각보다 엄청 크다.

 

 

해결 방법은 set 대신 priority_queue를 이용하는 것이다.

우리가 set을 쓴 이유는 "원소 추가", "최솟값 찾기", "어떤 원소 $x$ 삭제"가 가능한 자료구조가 필요했기 때문인데, 특정 테크닉을 사용하면 놀랍게도 우선순위 큐로 특정 원소 삭제를 구현할 수 있다!!

 

https://blog.naver.com/jinhan814/222512213833

Theme 02. STL 자료구조 _ set을 priority_queue로 대체하는 테크닉

 

priority_queue는 상수가 정말 작으므로, set을 pq로 대체하면 별탈없이 문제를 풀 수 있다.

 

---

 

사실 위 방법은 고정된 $d$에 대해 $O(N\log{N})$으로 판별하는 알고리즘인데, 이를 $O(N)$으로 최적화할 수 있다.

배열을 정방향/역방향으로 한 번씩 훑으면서 (다음 원소 - 현재 원소) 값이 $d$ 이하가 되도록 맞춰주는 방식이다. 이 글에서 설명한 알고리즘에서 처리 순서를 바꾼 것이라 볼 수 있을 것 같다. 증명은 exercise로 남겨두겠다 😝

 

이 문제의 풀이를 설명한 블로그 글들을 보면 대부분이 "1. 파라메트릭 서치를 쓰자. 2. 결정함수 이렇게 양방향으로 돌리면 끝!" 형식의 설명 방식을 취하고 있다. 심지어는 결정 함수에 대한 설명이 전혀 없는 글도 많이 보였다.

안타깝게도, 이 문제를 풀다 막혀서 풀이를 찾아보는 사람 입장에선 어쩌다 그런 풀이가 나오게 된 건지도 알 수 없고, 그 풀이가 왜 성립하는지도 알 수 없을 것이다. (나는 1700번 멀티탭 스케줄링 문제로 비슷한 경험을 한 적이 있다.) 이걸 사람이 어떻게 생각하지..하는 좌절감에 빠지게 될 가능성이 높다. 문제를 푸는 사람으로서 정말 기분 나쁜 상황이 아닐 수 없다.

 

다른 사람의 풀이를 보면서 얻을 수 있는 가장 중요한 것은 풀이뿐만 아니라 그 사람의 사고 과정이라고 생각한다. 또한 문제를 풀었는데 그 풀이가 왜 옳은 풀이인지 모른다면 그 문제를 푼 것이 절대 아니다. (물론 대회에서는 어떻게든 풀어내는 것이 중요하겠지만)

앞으로는 두 가지 모두 잘 설명된 블로그 글들이 많아졌으면 좋겠다. 😊😊