[Python] 백준 2217 로프

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

 

문제 분석

• N개의 로프
• 각 로프는 들 수 있는 물체의 중량이 서로 다를 수 있다.
• 로프를 병렬로 연결하여 중량이 w인 물체를 들어올릴 때, 각 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.
• 각 로프의 정보가 주어졌을 때, 로프들을 사용하여 들어올릴 수 있는 물체의 최대 중량은?
• 모든 로프를 다 사용하지 않아도 된다.

 

풀이

• 중량은 정확하게 w/k로 나눔으로 k개의 로프에 대해 최대로 들 수 있는 무게는 k중 가장 적게 들 수 있는 중량 x k 이다.
• 로프의 길이에 대해 내림차순으로 정렬한 뒤
• 각 로프가 추가될 때마다 들 수 있는 최대 중량을 저장한다.
• 1 <= n <= 100,000
• dp ?

 

코드 설계

• 작은 로프에 대해 로프가 들 수 있는 무게가 달라지므로 내림차순으로 정렬한다.
• 이전의 무게와 현재의 무게 ( i번째의 로프가 현재까지의 로프 갯수만큼) 비교

 

정답 코드

1차 - 시간초과

import sys
input = sys.stdin.readline

n = int(input())
rope = []
for _ in range(n) :
    rope.append(int(input()))
rope.sort(reverse=True)
max_weight = rope[0]

for i in range(1, n) :
    max_weight = max(max_weight, min(rope[:i+1])*(len(rope[:i+1])))

print(max_weight)

 

2차 - dp

import sys
input = sys.stdin.readline

n = int(input())
rope = []
for _ in range(n) :
    rope.append(int(input()))
rope.sort(reverse=True)

dp = [0 for _ in range(n)]

dp[0] = rope[0]

for i in range(1, n) :
    dp[i] = max(dp[i-1], rope[i] * (i+1))

print(dp[n-1])