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)
'알고리즘' 카테고리의 다른 글
백준 9252 : LCS (0) | 2024.11.05 |
---|---|
백준 1026 : 보물 (1) | 2024.10.12 |
백준 1931 : 회의실 배정 (1) | 2024.10.09 |
백준 1193 : 분수찾기 (0) | 2024.10.08 |
당신의 기울기는 얼마입니까? : 시간복잡도와 공간복잡도 (5) | 2024.10.07 |