[그리디]백준 2217 로프 | 파이썬 풀이

문제 링크

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

문제 해석

간단히 설명하자면, 문제에서 N개의 로프로 중량이 w인 물체를 들 때, w/N만큼의 무게가 분산된다고 한다.

예를 들어 15의 중량을 들어올리는 로프는 한 개로는 15밖에 들지 못하지만, 10, 15의 중량을 들 수 있는 두 로프로는 10, 10씩 들어올려 총 20의 물건을 들어올리게 되는 것이다.

그렇다면 로프가 5, 10, 15일 때는 어떨까? 5, 5, 5씩 무게가 분산되어 최대 15의 무게를 들어올릴 수 있게 된다. 따라서 무조건 많은 로프를 들어올린다고 해서 유리한 것이 아니다.

문제 풀이

여기서 떠오르는 먼저 떠오르는 생각으로는, 50 40 10의 물체를 들어올리는 로프 3개가 있을 때, 50과 40의 로프 두개로는 물체를 80까지 들어올릴 수 있지만 10이 들어가는 순간 10*3=30밖에 들어올리지 못하기 때문에 이 로프의 하중(?)배열을 정렬 후에 50 한번, 50, 40 한번, 50, 40, 10 한번씩 진행하면서 무게가 낮아지는 순간 반복문을 나오는 방법을 생각해봤다. 아무래도 N이 최대 10만이다 보니 심적 부담이 있었나보다. 정렬도 한 번 해야하고, for문도 돌아야 하니까..? 사실 시간초과가 날 수치는 아니긴 했다.

그런데 이 방법에는 문제가 있었다. 예를 들어 입력이
4
1
1
1
3
이렇게 주어진다고 해보자. 4개의 로프인데 각각 무게가 1, 1, 1, 3을 견디는 로프이다. 위의 로직대로라면 차례대로 대입해 보았을 때,
1) 3 로프 하나로는 3의 무게를 들 수 있다.
2) 1, 3 로프 두개로는 1*2=2의 무게를 들 수 있다. 여기서 들 수 있는 중량이 낮아지니 바로 빠져나온다.

이렇게 되는데, 막상 마지막까지 계산해본다면 1, 1, 1, 3의 로프로는 1*4 = 4의 중량이 들어진다.
이 때문에 마지막까지 다 돌려봐야 한다는 생각을 했고 결국 모든 경우의 수를 구해서 정답을 맞힐 수 있었다.

import sys
In = sys.stdin.readline

# 입력
N = int(In())
arr = [0]*N
for i in range(N):
    arr[i] = int(In())

# 정렬
arr.sort()

memo = 0 # 들 수 있는 무게의 최댓값을 메모할 변수

# 제일 큰 수 부터 차례로 내려가면서 들 수 있는 무게 계산
for i in range(N-1, -1, -1):
    memo = max(memo, arr[i] * (N - i))
print(memo)

또한 여기서 새로운 사실을 알았는데, 파이썬에서는 입력 시 sys를 import해서 sys.stdin.readline를 이용해 입력을 받는다는 것이다. 이유는 아래 링크에 있다.
https://www.acmicpc.net/board/view/855
여러 줄을 반환 받아야 할 때는 위와 같이 코드를 짜야한다. 그렇지 않고 input()을 사용했을 때는,,

이런 차이를 경험할 수 있다. 난 백준 서버탓인줄 알았다.(하지만 언제나 내 탓이었다.)