백준 2790 - F7 풀이 및 수학적 증명

문제 링크: 백준 2790번 - F7

Prologue

이 문제는 접근하기 까다로웠던 문제였습니다. 우승한 가능성이 있는 사람을 모두 골라야 하는 부분을 어떻게 구현해야 할지 고민이 많았습니다. $N$의 크기가 $300000$이라 단순히 한 명 씩 전부 우승할 수 있을지 없을지를 구하면 안된다는 것을 알고 있었지만, 일단 마땅히 떠오르는 방법이 없었기에 처음에는 아래와 같이 코드를 짜보았습니다.

import sys
i=sys.stdin.readline

b=[]
n=int(i())
for _ in range(n):b.append(int(i()))
b.sort(reverse=True)

m=[i for i in range(1,n)]
for x in range(n-1,-1,-1):
    m.insert(x, n)
    c=[i+j for i,j in zip(b,m)]
    if c[x]==max(c):break
    m.pop(x)
print(x+1)

리스트 $b$에 레이서들의 현재 점수를 받아 내림차순으로 정렬한 다음, 리스트 $m$에 $1$부터 $n$까지의 점수를 오름차순으로 담아두고, 최고점 $n$을 $m$의 맨 뒤에서부터 앞으로 한 칸씩 옮기며 $m$을 $b$와 더해 해당 선수가 최고점을 얻을 수 있는지 판단했습니다. (지금보니까 왜 insert를 썼는지 모르겠네요)

당연하겠지만 결과는 시간초과였습니다. 위 코드의 시간 복잡도는 $O(n^2)$이므로 최악의 경우에는 $900$억 번 이상의 계산이 소요될 것이기 때문이었습니다. 이것보다 좀 더 빠르고 효율적인 방법이 필요했습니다.

Problem Analysis

문제를 단순화시키면 이렇습니다.

• $0$ 이상의 정수 $N$개로 이루어진 리스트 $L$이 주어진다.
• $1$부터 $N$까지의 수들을 $L$의 각 원소에 하나씩 배정하여 더할 때, $L$의 인덱스 $k$에 대하여 $\max(L)=L[k]$를 만족할 수 있는 $k$의 개수는?

기본적인 추측부터 시작해봅시다. $L[k]$가 $A$의 최댓값이 될 가능성을 최대한 높이려면 $L[k]$에 가장 큰 수인 $N$을 배정해야 할 겁니다. 그리고 $L$의 나머지 원소들에는 작은 원소부터 큰 수들을 차례로 배정해야 합니다. 그래야 수를 더하기 전에 $L[k]$보다 더 컸던 원소들이 수를 더한 후 $L[k]$보다 작아질 가능성이 높아지기 때문입니다.

좋습니다. 그럼 정렬을 먼저 해둬야겠군요. 이제 내림차순으로 정렬된 $L$을 $A$로 정의하겠습니다.

$A=[a_0 ,~a_1,~a_2,~\cdots,~a_{N-1}] \quad (a_n\geq a_{n+1} ~{\rm for}~\forall n;~~ \forall a_k \in L)$

$1$부터 $N$까지의 수들을 $A$의 각 원소에 하나씩 배정하여 더할 때, $\max(A)=A[k]$를 만족할 수 있는 $k$의 개수를 알기 위해선 단순하게는 모든 $k$에 대해 $A[k]$가 최댓값이 될 수 있는지 전부 구해보면 됩니다. 그러나 이런 알고리즘은 시간초과가 나므로 이 기본적인 과정을 자세히 살펴보고 간단히 만들 수 있는 구석이 있나 살펴보겠습니다.

Algorithm

함수 $f_k$를 $A[N-k-1]$에 가장 큰 수를 배정하고 $A[N-k-1]$을 제외한 나머지 $A$의 원소에는 작은 원소 순서대로 큰 수들을 차례대로 배정하는 것이라고 정의해봅시다. 이 뒤로는 혼동을 방지하기 위해 "$f_k$를 적용했을 때의 $A$"를 $A_k$로 작성하도록 하겠습니다.

$f_k$의 규칙을 알아보기 위해 $k$값에 따라 나열해보면

$f_0:A_0=[a_0+1,\quad \cdots,\quad a_{N-3}+N-2,\quad a_{N-2}+N-1,\quad \textcolor{#ed6851}{a_{N-1}+N}]\\ \ \\ f_1:A_1=[a_0+1,\quad \cdots,\quad a_{N-3}+N-2,\quad \textcolor{#ed6851}{a_{N-2}+N},\quad a_{N-1}+N-1]\\ \ \\ f_2:A_2=[a_0+1,\quad \cdots,\quad \textcolor{#ed6851}{a_{N-3}+N},\quad a_{N-2}+N-2,\quad a_{N-1}+N-1] \\ \ \\ \vdots \\ \ \\ f_{N-1}:A_{N-1}=[\textcolor{#ed6851}{a_{0}+N},\quad \cdots,\quad a_{N-3} + N-3,\quad a_{N-2}+N-2,\quad a_{N-1}+N-1]$

입니다. $f_{k-1}$과 $f_k$사이의 규칙이 보이시나요? $f_{k-1}$에서 $A_{k-1}[N-k-1]$에는 $k$를 더하고, $A_{k-1}[N-k]$에는 $k$를 빼면 $f_k$이 됩니다. 이것은 수학적 귀납법으로 쉽게 확인이 가능한데, 어차피 눈으로도 보이니 여기서는 굳이 적지 않도록 하겠습니다.

위 사실을 이용하여 $f_k$를 새로 정의할 수 있습니다.

$f_k= \begin{cases} 0\le n \lt N \footnotesize \mathsf{인~모든}\normalsize~n\footnotesize \mathsf{에~대해}\normalsize~A[n]\footnotesize \mathsf{에}\normalsize~n+1 \footnotesize \mathsf{을~더한다.}\normalsize\quad(k=0) \\ f_{k-1} \footnotesize \mathsf{에서~}\normalsize A_{k-1}[N-k-1]\footnotesize \mathsf{에는~}\normalsize k\footnotesize \mathsf{를~더하고}\normalsize ~A_{k-1}[N-k]\footnotesize \mathsf{에는~}\normalsize k\footnotesize \mathsf{를~뺀다.}\normalsize\quad(0<k<N) \end{cases}$

조금 설명이 어려운데 파이썬 코드로 보면 이해가 수월할 겁니다. 이 코드는 $f_0$부터 $f_{N-1}$까지 함수를 돌리는 코드입니다.

for n in range(N): #k=0
	A[n]+=n+1
for k in range(1, N): #k=1,2,3,...,N-1
    A[N-k]-=k
    A[N-k-1]+=k

이 함수를 새롭게 정의하고 나서 곰곰히 고민해보니, 어떠한 생각에 도달했습니다. 그 생각은, '만약에 $k=0$부터 시작해 $f_k$ 함수를 돌리다가 ${\rm max}(A_k)=A_k[N-k-1]$을 만족하게 되면 $A_k[0]$부터 $A_k[N-k-1]$까지의 모든 원소들은 전부 최댓값이 될 수 있는 것 아닌가?'였습니다. 예를 들어보겠습니다.

$A=[9,7,5,4,2]$로 두면 $N=5$이고 $k$를 $0$부터 $4$까지 차례대로 변화시키며 $f_k$를 적용시켜보면

$f_0:A_0=[9+1,~7+2,~5+3,~4+4,~2+\textcolor{#ed6851}5]=[10,9,8,8,\textcolor{#ed6851}7] ~\quad\rightarrow\quad {\rm max}(A_0) \not =A_0[4]$

$f_1:A_1=[9+1,~7+2,~5+3,~4+\textcolor{#ed6851}5,~2+4]=[10,9,8,\textcolor{#ed6851}9,6] ~\quad\rightarrow\quad {\rm max}(A_1) \not =A_1[3]$

$f_2:A_2=[9+1,~7+2,~5+\textcolor{#ed6851}5,~4+3,~2+4]=[10,9,\textcolor{#ed6851}{10},7,6] \quad\rightarrow\quad \color{#06f}{\rm max}(A_2)=A_2[2]$

$f_3:A_3=[9+1,~7+\textcolor{#ed6851}5,~5+2,~4+3,~2+4]=[10,\textcolor{#ed6851}{12},7,7,6] \quad\rightarrow\quad \color{#06f}{\rm max}(A_3)=A_3[1]$

$f_4:A_4=[9+\textcolor{#ed6851}5,~7+1,~5+2,~4+3,~2+4]=[\textcolor{#ed6851}{14},8,7,7,6] ~\quad\rightarrow\quad \color{#06f}{\rm max}(A_4)=A_4[0]$

이처럼 한 번 최댓값이 될 수 있는 인덱스에 도달하는 순간 이후의 모든 값들은 전부 최댓값이 되는 것이 가능해 보였습니다. 이것은 다른 여러 예제를 통해 시험해봐도 마찬가지였습니다. 그럼 뭐다? 증명을 해봐야죠!

증명1) ${\rm max}(A_k)=A_k[N-k-1]$이면, ${\rm max}(A_{k+1})=A_{k+1}[N-k-2]$이다.

---

$f_k:A_k=[a_0+1,\quad \cdots,\quad a_{N-k-2}+N-k-1,\quad \textcolor{#ed6851}{a_{N-k-1}+N},\quad \cdots,\quad a_{N-1}+N-1]$

에서

${\rm max}(A_k)=A_k[N-k-1]=a_{N-k-1}+N$

라고 가정하자. 이때 $f_{k+1}$은

$f_{k+1}:A_{k+1}=[a_0+1,\quad \cdots,\quad \textcolor{#ed6851}{a_{N-k-2}+N},\quad a_{N-k-1}+N-k-1,\quad \cdots,\quad a_{N-1}+N-1]$

이고, $A_{k+1}[N-k-2]$와 $A_{k+1}[N-k-1]$ 이외의 나머지 원소들은 모두 변동 없이 동일하므로 이 둘만 비교하면 된다.


$A$는 내림차순으로 정렬된 리스트이므로

$a_{N-k-2} \ge a_{N-k-1}$

이다. 따라서

$a_{N-k-2}+N \ge a_{N-k-1}+N$

즉, $f_k$에서 ${\rm max}(A_k)=A_k[N-k-1]$였는데 그것보다 같거나 큰 원소가 $f_{k+1}$에서 $A_{k+1}[N-k-2]$로 등장했고 두 원소 이외의 나머지 원소들은 전부 그대로이므로 $f_{k+1}$에서 ${\rm max}(A_{k+1})=A_{k+1}[N-k-2]$이다.

---

따름정리1) ${\rm max}(A_k)=A_k[N-k-1]$이라면

${\rm max}(A_k) \le {\rm max}(A_{k+1})$

알고리즘의 시간을 비약적으로 단축시킬 수 있는 명제가 증명되었습니다! 이제 가장 처음으로 ${\rm max}(A_k)=A_k[N-k-1]$를 만족하는 $k$만 찾으면 답으로 $N-k$을 출력하면 끝입니다.

그렇지만 이것으로는 부족합니다. ${\rm max}()$함수는 기본적으로 $O(n)$입니다. 이것을 해결하기 위해 다시한번 예를 집중해서 볼까요?

$A=[9,7,5,4,2]$일 때

$f_0:A_0=[9+1,~7+2,~5+3,~4+4,~2+\textcolor{#ed6851}5]=[10,9,8,8,\textcolor{#ed6851}7] ~\quad\rightarrow\quad {\rm max}(A_0) \not =A_0[4]$

$f_1:A_1=[9+1,~7+2,~5+3,~4+\textcolor{#ed6851}5,~2+4]=[10,9,8,\textcolor{#ed6851}9,6] ~\quad\rightarrow\quad {\rm max}(A_1) \not =A_1[3]$

$f_2:A_2=[9+1,~7+2,~5+\textcolor{#ed6851}5,~4+3,~2+4]=[10,9,\textcolor{#ed6851}{10},7,6] \quad\rightarrow\quad \color{#06f}{\rm max}(A_2)=A_2[2]$

$f_3:A_3=[9+1,~7+\textcolor{#ed6851}5,~5+2,~4+3,~2+4]=[10,\textcolor{#ed6851}{12},7,7,6] \quad\rightarrow\quad \color{#06f}{\rm max}(A_3)=A_3[1]$

$f_4:A_4=[9+\textcolor{#ed6851}5,~7+1,~5+2,~4+3,~2+4]=[\textcolor{#ed6851}{14},8,7,7,6] ~\quad\rightarrow\quad \color{#06f}{\rm max}(A_4)=A_4[0]$

왜 ${\rm max}(A_0) \not =A_0[4],~{\rm max}(A_1) \not =A_1[3]$일까요? 그것은 다른 큰 수를 넘지 못했기 때문일 겁니다. 바꿔 말하면, $A_0[4]$와 $A_1[3]$모두 ${\rm max}(A_0)$보다 작기 때문입니다. 그리고 $A_k[N-k-1]$가 ${\rm max}(A_0)$을 넘어가는 순간, 답은 $N-k$입니다.

증명2) $A_k[N-k-1]={\rm max}(A_k)$의 필요충분조건은 $A_k[N-k-1] \ge {\rm max}(A_0)$이다.

---

수학적 귀납법을 이용한다.

1. $k=0$일 때, 자명하다.
   
   

2. $k=s$일 때, $A_s[N-s-1]={\rm max}(A_s)$이면 $A_s[N-s-1] \ge {\rm max}(A_0)$이고 역도 성립한다고 가정하자.
   
   

3.  

   • $(\implies)$
     $A_s[N-s-1]={\rm max}(A_s)$이면 증명1에 의해 $A_{s+1}[N-s-2]={\rm max}(A_{s+1})$이고, 따름정리1에 의해 ${\rm max}(A_{s+1}) \ge {\rm max}(A_s)=A_s[N-s-1] \ge {\rm max}(A_0)$.
     
     즉, $A_s[N-s-1]={\rm max}(A_s)$이면
     
     
     $A_{s+1}[N-s-2]={\rm max}(A_{s+1}), \\ \ \\ A_{s+1}[N-s-2] \ge {\rm max}(A_0)$
     
     이 전부 유도되고 이것은 $k=s+1$일 때도 가정이 $\implies$ 방향으로 성립함을 나타낸다.
     
     
   • $(\impliedby)$
     $A_s[N-s-1] \ge {\rm max}(A_0)$이면 $a_{N-s-1}+N \ge {\rm max}(A_s)$이고 $a_{N-s-2}\ge a_{N-s-1}$이므로
     
     
     $A_{s+1}[N-s-2]=a_{N-s-2}+N \ge a_{N-s-1}+N=A_s[N-s-1]= {\rm max}(A_0)\\ \ \\ \therefore A_{s+1}[N-s-2] \ge {\rm max}(A_0)$
     
     또한, 증명1에 의해 $A_s[N-s-1]={\rm max}(A_s)$이면 $A_{s+1}[N-s-2]={\rm max}(A_{s+1})$임을 얻을 수 있다.
     
     
     즉, $A_s[N-s-1] \ge {\rm max}(A_0)$이면
     
     
     $A_{s+1}[N-s-2] \ge {\rm max}(A_0), \\ \ \\ A_{s+1}[N-s-2]={\rm max}(A_{s+1})$
     
     이 전부 유도되고 이것은 $k=s+1$일 때도 가정이 $\impliedby$ 방향으로 성립함을 나타낸다.
     
     

4. 3에 의해 주어진 명제는 참이다.

Code

import sys
i=sys.stdin.readline

A=[]
N=int(i())
for _ in range(N):A.append(int(i()))
A.sort(reverse=True)

for n in range(N):A[n]+=n+1
M=max(A)
if A[N-1]==M:print(N);exit()

for k in range(1, N):
    A[N-k]-=k
    A[N-k-1]+=k
    if A[N-k-1]>=M:print(N-k);exit()

PyPy3 기준 240ms로 굉장히 코드가 빨라졌습니다. 맨 처음 코드와 비교해보면 그 차이가 크게 느껴지네요.

Epilogue

그리디 알고리즘의 가장 어려운 부분은 "과연 이 알고리즘이 올바른 정답을 반환할 것인가?"라고 생각합니다. 정답을 반환하는지 아닌지를 확실하게 하기 위해선 증명이 필요하죠. 저도 감으로 코드를 짜고 "맞춰서 증명하기"의 전략을 자주 사용하긴 하지만 가끔은 이렇게 정확히 증명해보는 일도 필요하다고 생각해 글을 작성하게 되었습니다. 사실 증명이 제가 봐도 깔끔한 편은 아닌데 혹시 이 글을 끝까지 이해하며 읽으신 분이 있을지는 모르겠지만, 만약 존재한다면 경의를 표하고 싶습니다. 읽어주셔서 감사합니다.