[그리디] 백준 2217번 로프 Python 풀이

문제 요약

물체를 들어올릴 수 있는 N(1 ≤ N ≤ 100,000)개의 각기 다른 종류의 로프가 있다. 각 로프가 들 수 있는 물체의 중량이 서로 다를 수 있지만, 로프를 병렬로 연결하면 각 로프에 걸리는 중량을 나눌 수 있다.

(예 : k개의 로프로 중량이 w인 물체를 들어올리면, 각 로프에는 모두 w/k 만큼의 중량이 걸림)

각 로프에 대한 정보가 주어질 때, 해당 로프들로 들어올릴 수 있는 물체의 최대 중량을 구하는 프로그램을 작성하라.

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

백준 2217번 문제 바로가기

입력

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

출력

첫째 줄에 답을 출력한다.

입출력 예시

입력	출력
2 10 15	20

작성 코드

정답

import sys

N = int(sys.stdin.readline())
rope = list()
max_kg = 0

# N개의 로프에 대한 정보 입력
for _ in range(N):
    rope.append(int(sys.stdin.readline().strip()))
# 로프 정보를 오름차순 정렬
rope.sort()
# 로프를 사용해 들어올릴 수 있는 최대 중량 구하기
for i in range(N):
    max_kg = max(max_kg, int(rope[i]) * (N - i))
# 결과값 출력
print(max_kg)

피드백

처음에는 아무 생각 없이 최저값 * N을 출력했다. 모든 조건을 고려하는 습관을 들이기 위해 노력하자.

내가 찾은 패턴

• 계산하고자 하는 로프의 정렬된 순서에 따라 계산이 달라진다.
• 현재_로프_중량 * (전체_로프_개수 - 현재_로프_순서) = 들어올릴_수_있는_중량

깨달은 것

• 모든 조건을 고려하여 해결 방법을 찾는 습관을 들이자
• 이전에 배운 것을 적용하기
  이런게 있구나, 하고 넘어간다고 사용할 수 있게 되는 것이 아니다. 공부한 내용이 있다면 꼭 적용해보자!(이 포스팅에서는 sys.stdin.readline()) 막상 사용하려고 하면 기존에 공부한 내용 이상으로 공부해야 할 때가 더 많다는 걸 기억하자.