[백준 BOJ_2217] 로프 Python 풀이

출처: 백준 온라인 저지

문제

풀이

동적계획법으로 풀어 보겠습니다.

문제의 $k$개의 로프를 사용하여 중량이 $w$인 물체를 들어올릴 때, 각각의 로프에는 고르게 $\frac{w}{k}$만큼의 중량이 걸리게 된다는 부분을 다시 이해하면 최대로 올릴 수 있는 중량은 아래와 같습니다.

로프 중 가장 적은 중량의 로프 * 연결하는 로프의 수

그래서 로프가 버틸 수 있는 중량을 list로 받아준 뒤, list를 오름차순으로 정렬해줍니다.

cache[i]에는 ropes[i]의 로프부터 나머지 로프를 모두 사용했을 때의 최대 중량을 저장해줍니다.

오름차순으로 정렬해준 ropes의 나머지 로프들(ropes[i+1:])은 최소 ropes[i]만큼은 버틸 수 있기 때문에(ropes[i+1:] >= ropes[i]) 다 포함해 주는 것이 최대 중량입니다.

그래서 cache의 값은 다음과 같이 됩니다.

cache[i] = ropes[i] * (i번째 로프를 포함한 나머지 로프의 개수)

for loop을 N만큼 돌려 cache를 update해주고 cache의 max값을 출력해줍니다.

코드

N = int(input())
ropes = [ int(input()) for _ in range(N) ]
ropes.sort()
cache = [0 for _ in range(N)]
for i in range(N):
    cache[i] = ropes[i]*(len(ropes)-i)
print(max(cache))