백준 2217 : 로프

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

 

그리디 문제이다.

풀이를 찾는데 살짝 헤맸는데, 그 과정을 주르륵 써보도록 하겠다.

생각의 흐름

알고리즘 분류 찾아서 들어간거라 그리디라는 건 알고 있었지만,

완전탐색을 하게되면 얼마나 걸릴까 생각해보았다.

 

가능한 모든 로프의 경우의 수를 찾는 것이기 때문에,

각 로프마다 (넣는다, 안넣는다) 2개의 선택지가 있어서 $O(2^n)$이 된다.

$N$이 최대 100,000이었기 때문에 최소한 $NlogN$정도의 복잡도는 필요했다.

 

그래서 다음 단계로 그리디하게 생각해보기로 했다.

 

첫번째 삽질

가장 처음했던 가정은, "값이 큰 로프부터 넣다가, 최대 중량 값이 작아지는 시점에 그만둔다" 였다.

로프 값이 $t_{1} > t_{2} > t_{3} > ... > t_{n}$ 이렇게 있으면,

$t_{1}$ 고르고 최대 중량 값 계산해보고,

$t_{1}, t_{2}$ 고르고 최대 중량 값 계산해보고,

...

계산을 하다가,

바로 직전에 계산한 최대 중량값(A)보다 지금 계산한 최대 중량값이(B) 작아지면,

바로 직전에 계산한 최대 중량값(A)이 답이라는 가정이었다.

 

그러려면, 앞으로 계산할 최대 중량값들(C)이

바로 직전에 계산한 최대 중량값(A)보다 작다는 걸 증명해야했다.

 

앞서서의 표현처럼, 로프 N개를 아래와 같이 표현했을 때,

$t_{1} > t_{2} > t_{3} > ... > t_{n}$

증명해야할 내용은 아래와 같았다.

$if \ kt_{k} > (k+1)t_{k+1}, then \ kt_{k} > it_{i} \ (i > k+1, 1<=k<=n-1)$

 

$k=1$일 때를 예로 풀어 설명해보겠다.

우선 식을 풀면, $k=1$이면, $if \ t_{1} > 2t_{2}, then \ t_{1} > (i+1)t_{i+1} \ (i>1)$가 된다.

 

여기서 중요한 점은,

로프를 가장 큰 순서대로 선택하는 경우,

이전에 선택한 더 큰 값의 로프들이 감당하는 최대 무게(D)는,

지금 선택한 로프가 감당할 수 있는 최대 무게(E)가 된다는 것이다.

 

예를 들어 문제의 예시처럼 로프 2개가 있고, 각각 15/10만큼의 무게를 감당할 수 있다고 하자.

가장 큰 순서대로 로프를 선택하게 되면 15 -> 10 이렇게 선택하게 된다.

10을 선택할 때 잘 보면, 이전에 선택했던 더 큰 값들의 로프들(예시에선 값이 15인 로프)이 감당하는 최대 무게(D)는

지금 선택한 로프가 감당할 수 있는 최대 무게(E)인 10이 된다.

 

지금 선택한 로프가 가장 약하기 때문에, 그 로프를 기준으로 계산한다고 이해해도 되겠다.

 

그러면 이제 아까 봤던 식이 이해될 것 같다.

$k=1$이면, $if \ t_{1} > 2t_{2}, then \ t_{1} > t_{i} \ (i>2)$의 의미는,

 

가장 큰 로프 한개만 선택했을 때 최대 무게 $t_{1}$보다

가장 큰 로프 한개와 그 다음으로 큰 로프까지 총 2개를 선택했을 때의 최대 무게 $2t_{2}$가 더 크면,

(= 최대 무게 합이 역전되는 시점이 오면)

가장 큰 로프 한 개만 선택했을 때 최대 무게 $t_{1}$보다

가장 큰 로프부터 i개 선택했을 때 최대 무게 $it_{i}$가 더 크다.

라는 뜻이다.

 

그런데 이건 $i=3$일 때 바로 반박된다.

$i=3$이면, 식이

$k=1$이면, $if \ t_{1} > 2t_{2}, then \ t_{1} > 3t_{3}$ 로 바뀐다.

 

우리의 가정에서,

$t_{1} > t_{2} > t_{3}$ 였고,

$t_{1} > 2t_{2}$인 상황이므로,

$\frac{1}{2}t_{1} > t_{2} > t_{3}$이 된다.

 

그러니까 $t_{1} > 2t_{3}$이긴 한데, $t_{1} > 3t_{3}$이라고 할 수는 없다.

따라서, 내 첫번째 삽질이 이렇게 끝나버렸다.

두번째 삽질(이자 정답)

그런데 조금만 더 생각해보니 답은 가까운 곳에 있었다.

내가 첫번째 삽질을 하면서도 무의식적으로 했던 가정인 것인데,

어떤 로프(F)를 포함하고자 할 때, 그 로프보다 큰 값의 로프들(G)은 무조건 포함하는 것이 이득이다.

 

이건 뭐 굳이 증명이 필요하지 않다고 생각한다.

어떤 로프(F)보다 큰 값의 로프들은(G) 포함시키면 포함시킬 수록

감당할 수 있는 무게의 총합에 어떤 로프(F)가 감당하는 무게만큼 추가되는 것이기 때문이다.

 

그리고, 감당할 수 있는 무게의 총합을 구하는 것은

그냥 선택한 로프 중 가장 작은 로프의 값에다가 선택한 로프의 총 개수를 곱하기만 하면 된다.

 

첫번째 삽질에서 얻은 결론을 정리하면

아무리 로프를 큰 순서대로 정렬한다고 해도,

이후의 값들을 계산해보지 않으면, 지금 이 값보다 작다고 보장할 수 없다(=계산을 다 해봐야 한다)

였다.

 

근데, 두번째 삽질에서 얻은 결론은,

그냥 그 뒤에도 계산해보면 된다. 인 것이다

그래도 시간복잡도가 $O(n)$일 뿐이니까

 

코드

N = int(input())

ropes = []
for _ in range(N):
  ropes.append(int(input()))

ropes.sort(reverse=True)

maxVal = -1
for (i, rope) in enumerate(ropes):
  val = rope * (1+i)
  if val > maxVal:
    maxVal = val
print(maxVal)