[백준 2217번] 로프 (python)

문제

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

 

기록

(greedy 1일차) 내가 세운 규칙이 백퍼센트 맞다고 생각하고 의심안하고 있다가 구글링 해보고 틀린 걸 알았다. 질문리스트 봤는데 다른 사람들도 놓치는 부분인 것 같아서 적어놓는다.

 

* rope 정렬한 뒤 순차적으로 weight 계산할 때 값이 커지다가 작아지는 지점을 찾으면 안 되고, 끝까지 배열 돌면서 가장 큰 값 찾아야 한다. (반례 '20 9 7' -> 21)

 

코드

from sys import stdin

N = int(stdin.readline())
ropes = []
for _ in range(N):
    ropes.append(int(stdin.readline()))
ropes.sort(reverse=True)

maxweight = 0
for i in range(N):
    weight = ropes[i]*(i+1)
    if weight>maxweight:
        maxweight = weight

print(maxweight)

1. rope 배열 저장한 뒤 정렬

배열 정렬해야 뒤에서 순차적으로 weight 계산이 가능하다.

 

2. 배열 끝까지 돌면서 가장 큰 weight 찾기

weight가 한 번 커지다가 작아지는 패턴이 아니라, 그때그때 달라질 수 있기 때문에 끝까지 돌면서 가장 큰 중량 찾아야 한다!