[백준 알고리즘] 2217번 : 로프 (Python) 문제 풀이

문제

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

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

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

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 답을 출력한다.

 

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

2217번: 로프

 

문제풀이 : 

이 문제는 그리디 알고리즘을 이용하여, 푸는 문제이다. 

문제의 최적해 값은 "로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량" 을 구하는 것이다.

 

단, 조건이 하나가 붙는다. 

모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

 

이는 예를들어서, 

4개의 로프가 주어졌을때, 각 로프가 들 수 있는 최대 중량이 1,2,3,4일 경우

최적해 값은 6이다. 왜 일까?

1,2,3,4중 3개의 로프를 사용하여, 그중 가장 작은 2의 로프 값만큼 3,4의 로프도 그만큼 중량을 분담한다면, 

2x3가 되어 6이 된다. 

혹은 

3,4만 사용하여 제일 작은 3의 로프값만큼 4도 그만큼 분담하여 

3x2가 되어 6이 된다.

 

예제1를 보면, 2개의 10,15 로프가 주어진다. 

10로프는 15만큼의 중량을 분담하지 못하지만, 15는 10만큼의 중량을 부담할 수 있다. 

그렇기에 10x2가 되어 답이 20이된다. 

 

이제 간단해진다. 

주어진 로프를 정렬하여, for문을 이용하여 하나씩 값을 구해본 이후 최대값을 뽑으면 된다. 

num = int(input())
ropes = []
list_answer = []
for i in range(num) :
    rope = int(input())
    ropes.append(rope)
 
ropes = sorted(ropes)
 
for i in range(num):
    list_answer.append((i+1)*ropes.pop())
 
print(max(list_answer))

https://github.com/ois0886/BJ_Python/blob/main/BJ_2217.py

GitHub - ois0886/BJ_Python