백준 온라인 저지 - 8232. Leveling Ground

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

8232번: Leveling Ground

미친 문제이다.. 풀이를 보고 소름 돋았던 문제.

혼자 힘으로는 못풀었다. 구글에 검색했는데 중국 사이트 풀이가 나와서 수식을 참고해서 풀었다.

 

(해당 블로그 링크)

https://blog.csdn.net/weixin_30808693/article/details/98612146?ops_request_misc=%7B%22request%5Fid%22%3A%22158337835919725219908567%22%2C%22scm%22%3A%2220140713.130056874..%22%7D&request_id=158337835919725219908567&biz_id=0&utm_source=distribute.pc_search_result.none-task

 

문제 내용은 다음과 같다.

 

원소 N개의 정수 배열이 있다.(1<=N<=10^5) 두 자연수 A, B가 주어진다.(1<=A,B<=10^9) 부분 배열을 골라서(S[l, l+1, l+2, ...,r]) 해당하는 원소에 A 혹은 B 값을 더하거나 빼는 연산을 할 수 있다. 이를 통해 모든 원소를 0으로 만드는 최소 횟수를 구하는 문제이다.

 

예를 들어, N, A, B = 5, 2, 3 이고, 초기 배열이 S = {1, 2, 1, 1, -1} 이면 아래 5번의 동작으로 모든 원소를 0으로 만들 수 있다.

• 1~2번째 원소를 2 더한다.
• 1~2번째 원소를 3 뺀다.
• 2~5번째 원소를 2 더한다.
• 5번째 원소를 2 더한다.
• 2~5번째 원소를 3 뺀다.

 

 

 

 

 

----- 풀이 (스포주의) -----

 

우선 요구하는 동작을 수행 불가능한 때는 최대공약수를 이용하면 미리 걸러놓을 수 있다.

$A$, $B$가 서로소이고 동작 수행이 가능한 상황만 고려하자.

 

 

연속된 구간을 통째로 더하거나 빼는 갱신을 할 때는 인접한 두 원소 사이의 차이 배열을 흔히 떠올리게 된다.

 

$D[i] = S[i] - S[i-1]$이라 두자. 부분 배열 $S[l:r]$을 $a$ 만큼 더하면 $D[l]$은 $a$ 증가하고, $D[r+1]$은 $a$ 감소한다. 나머지 값은 변화가 없다.

 

편의상 $S[0] = S[N+1] = 0$ 두고, $D$ 값을 1번째부터 $N+1$번째까지 계산해놓자.

 

최종적으로 모든 $D$ 배열의 원소를 0으로 만드는 것이 목적이다. 이는 아주 쉽다. 하지만 동시에 $S$ 배열의 모든 원소를 0으로 만드는 조건을 찾는 것이 까다롭다.

 

 

우선 $S$ 배열을 0으로 만드는 것은 잠시 생각하지 말고, 모든 $D$ 배열의 원소를 0으로 만들어보자.

$$ D[i] = A X[i] + B Y[i] $$

를 만족하는 $X[i]$, $Y[i]$는 확장 유클리드 호제법을 사용하여 찾을 수 있다.

디오판틴 방정식이므로 일반해는 각각 $X[i] = X_0[i] + k_i B$, $Y[i] = Y_0[i] - k_i A$ 꼴이다.

 

문제의 조건을 이용해서 $S[l:r]$ 구간을 $A$ 만큼 더하는 동작은, $X[l]$ 값을 1 더하고, $X[r+1]$ 값을 1 빼는 결과를 초래한다.

그러므로 $\sum X[i]$ 나 $\sum Y[i]$ 는 변하지 않는다.

역으로, $\sum X[i]$ 와 $\sum Y[i]$ 값이 초기값인 0과 같다면 문제에서 주어진 동작을 통해 $X$, $Y$ 배열의 구성을 만드는 것이 항상 가능하다.

 

결국 우리가 만들 배열 $X$, $Y$는 아래 두 조건을 만족하면 된다.

$$ \sum X[i] = 0 $$

$$ \sum Y[i] = 0 $$

하지만 $S[0] = S[N+1] = 0$ 이므로 $\sum D[i] = 0$이라는 점을 이용하면 오직

$$ \sum X[i] = 0 $$

을 만족하는 해만 찾아도 충분하다는 것을 알 수 있다.

 

$X$, $Y$ 배열을 만드는 비용, 즉 문제에서 주어진 동작의 최소 시행 횟수는

$$ \frac{1}{2} \left( \sum | X[i] | + | Y[i] | \right) $$

이다.

 

방정식의 일반해가 $X[i] = X_0[i] + k_i B$, $Y[i] = Y_0[i] - k_i A$ 였던 것을 기억하자.

각 $i$에 대해 $|X[i]| + |Y[i]|$는 $k_i$에 대한 볼록함수이다. 이 값을 최소로 하는 $k_i$는 삼분탐색을 통해 구할 수 있다.

 

각 $|X[i]| + |Y[i]|$를 최소로 하도록 $X$, $Y$ 배열을 건설했을 때,

$$ \sum X[i] > 0 $$

이라면 일부 $X[i]$ 값을 조금씩 빼주면 된다. 일반해의 특성에 따라 $X[i] := X[i] - B$, $Y[i] := Y[i] + A$로 갱신해주면 된다.

하지만 비용 증가량을 최소화하는게 중요하다.

$$ \left| X[i] - B \right| + \left| Y[i] + A \right| - \left| X[i] \right| - \left| Y[i] \right| $$

를 최소 힙에 넣어놓고 $\sum X[i] = 0$이 될 때까지 $X[i], Y[i]$ 값을 갱신해주면 된다.

 

$\sum X[i] < 0$ 일 때는 반대로 진행하면 된다.

 

 

 

정말 많은 것을 배웠던 문제이다.

 

연속 구간 합 갱신에서 인접 원소 차이 배열을 이용할 수 있다는 풀이를 들었던 것이 엊그제인 것 같은데, 이런 문제에서 응용이 가능할 줄 몰랐다.

 

또 다른 유형을 하나 소화하게 된 것 같아 정말 뿌듯하다.