[BOJ/BaekJoon] 백준 2217 로프 (Python / 파이썬)

BaekJoon BOJ 백준 2217 로프 문제는 로프의 개수, 각 로프가 버틸 수 있는 최대 중량이 주어졌을 때, 이 로프들을 이용하여 들어 올릴 수 있는 물체의 최대 중량을 구하는 문제이다.

 

BaekJoon 2217 로프 문제 정보

출처

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

알고리즘 분류

- 그리디 알고리즘 (greedy algorithm, 탐욕법)

난이도

- 실버 4 / Silver 4

 

로프 문제 요약

• 로프를 이용하여 이런저런 물체를 들어 올릴 수 있다.
• 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.
• 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다.
• k개의 로프를 사용하여 중량이 w인 물체를 들어 올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.
• 첫째 줄에 로프의 개수인 정수 N(1 ≤ N ≤ 100,000)이 주어진다.
  
• 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.
• 로프들을 이용하여 들어 올릴 수 있는 물체의 최대 중량을 구하여 출력한다.
• 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

문제 풀이 과정

임의로 몇 개의 로프를 고를 때에 들어 올릴 수 있는 중량을 무겁게 하려면 약한 로프들부터 제거하면 된다.

 

1. 로프의 개수 N, 각 로프가 버틸 수 있는 최대 중량을 리스트로 입력받는다.
2. 각 로프가 버틸 수 있는 최대 중량을 담은 리스트를 오름차순 정렬한다.
3. 모든 로프를 다 사용했을 때 들 수 있는 총무게부터
4. 가장 약한 로프를 하나 씩 제거해가면서 가장 강한 로프가 남을 때까지 반복하여 총무게를 구한다.
5. 로프를 제거해가며 총무게를 구할 때마다 그 값이 최대 중량이면 저장한다.
6. 저장된 최대 중량을 출력한다. 

 

코드 및 설명

• N - 로프의 개수
• weight - 각 로프가 버틸 수 있는 최대 중량을 담은 리스트
• result - 들어 올릴 수 있는 물체의 최대 중량

N = int(input())
weight = [int(input()) for _ in range(N)]
weight.sort()

result = 0
for i in range(N):
    result = max(result, weight[i] * (N-i))  # 들 수 있는 총 무게

print(result)

---

 

BaekJoon 백준 BOJ 2217 로프 문제를 파이썬 python으로 풀어보았다. 난이도는 Silver 실버 4이다.