로프(백준 2217번)

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?✓

---

난이도 체감

1. 최상

2. 상

3. 중✓

4. 하

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

(구현 연습이 필요하다)

문제

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

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

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

나의 풀이(정답 참고)

import sys
input=sys.stdin.readline

N=int(input().strip())
ropes=[]

for _ in range(N):
    r=int(input().strip())
    ropes.append(r)
ropes.sort()
r_count=len(ropes)
max_w=0
for i in range(len(ropes)):
    if ropes[i]*r_count>max_w:
        max_w=ropes[i]*r_count
    r_count-=1
print(max_w)

• 위 문제에서 로프를 모두 사용하지 않아도 되지만, 사용한다면 로프가 끊어지면 안된다. 즉, 줄이 버틸 수 있는 한계를 넘어가면 안된다.
• 가장 작은 중량을 버틸 수 있는 줄이 버틸 수 있는 무게를 k라고하고, 로프가 n개 있을 때, 최대 중량은 k*n이다.
• 그런데 만약 1,100을 각각 버틸 수 있는 로프가 있다고 할 때, 1을 버틸 수 있는 로프를 사용한다면 1*2=2가 되고, 사용하지 않는다면 100이 최대 중량이 된다. 따라서 가장 작은 중량을 버틸 수 있는 로프를 제외시키면서, 최대 중량값을 계산해 나가야 한다.