백준 - 2217번 로프 python 문제풀이 [Hellfer]

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

2217번: 로프

🔷 알고리즘 분류 - 수학, 정렬, 그리디 알고리즘  

난이도 - 실버 4

N개의 로프가 있고, 각 로프는 그 로프를 이용하여 물체를 들어 올릴 수 있는 최대 중량이 다르다는 것입니다.

로프를 병렬로 연결하면 각 로프에는 모두 동일한 중량이 걸리게 됩니다.

모든 로프를 사용할 필요는 없지만, 한 로프가 버틸 수 있는 최대 중량을 초과하면 그 로프는 찢어집니다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어 올릴 수 있는 물체의 최대 중량을 구해야 합니다.

즉, 이 문제는 주어진 로프들을 이용하여 들어 올릴 수 있는 물체의 최대 중량을 구하는 것입니다.

로프를 모두 사용하지 않고, 일부만 사용하여 물체를 들어 올릴 수 있습니다. 

 

하지만, 로프를 병렬로 연결하면 각 로프에 걸리는 중량은 모두 동일하므로, 가장 약한 로프를 기준으로 중량을 결정해야 합니다.

따라서 각 로프가 버틸 수 있는 중량을 내림차순으로 정렬한 후, 가장 약한 로프부터 시작하여 로프를 하나씩 추가하면서 최대 중량을 갱신하는 방식으로 문제를 해결할 수 있습니다. 

 

이렇게 하면, 어떤 로프를 사용하더라도 그 로프가 버틸 수 있는 최대 중량을 초과하지 않으면서 물체의 최대 중량을 구할 수 있습니다.

🔶문제 풀이 - 그리디 알고리즘을 이용한 풀이

n=int(input())  # 사용자로부터 로프의 개수 n을 입력받습니다.
result=[]

for _ in range(n):  # n번 반복합니다.
    x=int(input())  # 사용자로부터 로프가 버틸 수 있는 중량 x를 입력받습니다.
    result.append(x)  # 로프가 버틸 수 있는 중량 x를 result 리스트에 추가합니다.

y=sorted(result,reverse=True)  # result 리스트를 내림차순으로 정렬하고, 이를 y에 할당합니다.
       
result2=[]  # 최대 중량을 저장할 result2 리스트를 초기화합니다.
for i in range(len(y)):  # y의 길이만큼 반복합니다.
    result2.append((i+1)*y[i])  # 로프를 사용하는 순서(i+1)와 중량 y[i]를 곱합니다.
    
print(max(result2))  # result2의 최대값을 출력합니다.

🔶문제 이해하기

예를 들어, 5개의 로프가 20kg, 15kg, 10kg, 25kg, 20kg라고 가정해 보겠습니다.

이 경우, 각 로프가 버틸 수 있는 중량을 내림차순으로 정렬하면 다음과 같이 됩니다

- 25kg, 20kg, 20kg, 15kg, 10kg

이제 가장 약한 로프부터 시작하여 로프를 하나씩 추가하면서 최대 중량을 계산해 봅니다.

로프 1개를 사용할 경우, 가장 버틸 수 있는 중량이 큰 25kg의 로프를 사용하면 최대 25kg를 들어 올릴 수 있습니다.

로프 2개를 사용할 경우, 각 로프가 버틸 수 있는 중량은 모두 동일하므로, 두 로프 중 가장 약한 로프인 20kg의 로프를 기준으로 하면 최대 40kg(=20kg*2)를 들어 올릴 수 있습니다.

로프 3개를 사용할 경우, 세 로프 중 가장 약한 로프인 20kg의 로프를 기준으로 하면 최대 60kg(=20kg*3)를 들어 올릴 수 있습니다.

로프 4개를 사용할 경우, 네 로프 중 가장 약한 로프인 15kg의 로프를 기준으로 하면 최대 60kg(=15kg*4)를 들어 올릴 수 있습니다.

로프 5개를 사용할 경우, 다섯 로프 중 가장 약한 로프인 10kg의 로프를 기준으로 하면 최대 50kg(=10kg*5)를 들어 올릴 수 있습니다.

따라서 이 경우, 로프 3개를 사용하여 60kg의 물체를 들어 올릴 수 있으며, 이것이 최대 중량이 됩니다.