❓2217번 : 로프
〽️ 문제 요약
N개의 로프와 각 로프가 들 수 있는 중량이 주어지고, 그 중 일부만 선택해서 병렬로 연결하면 각 로프에 중량/로프 개수 만큼 무게가 고르게 걸리게 될 때, 들 수 있는 중량의 최대를 구하면 되는 문제
🤨 접근법
문제 이해가 좀 걸렸는데, 결국은 전체 N개의 로프 중 i개의 로프를 선택했을 때 i개의 로프 중 가장 적게 들 수 있는 로프의 중량 * i가 최대 들 수 있는 중량이 된다.
예를 들어 로프들이 [100, 1, 2, 3] 이렇게 주어질 때 100 로프 하나만 선택하면 100의 무게를 들 수 있지만 100로프와 3로프 두 개를 선택하면 6의 무게만 들 수 있다.
이를 위해 나는 N개의 로프에서 i(1 ≤ i ≤ N)개를 뽑는 모든 경우의 수를 고려해 min(로프)*로프 개수를 통해 답을 도출했지만 시간초과로 실패하였다.
본 문제는 그리디 알고리즘으로 해결할 수 있는 문제로, 특정 시점의 최적의 상황을 고려해야 한다. 그렇기 때문에 내림차순으로 큰 수부터 정렬 후 i(1 ≤ i ≤ N)개를 뽑는다면 모든 경우를 뽑지 않고 가장 큰 무게를 들 수 있는 로프를 포함해 순서대로 i개를 뽑는 경우만 고려하면 된다.
예를 들어 [10, 20, 30]의 로프가 주어질 때 정렬하여 [30, 20, 10]인 상태로 문제에 접근한다면, 로프 1개를 활용하는 경우 중 가장 큰 무게를 들 수 있는 경우는 가장 큰 무게를 들 수 있는 30 로프 1개를 고르게 되고, 로프 2개를 활용하는 경우는 무게 순서대로 30, 20을 활용하는 것이 결국 답으로 이어진다.
그리고 로프 i개를 뽑았다면, 그 로프들로 들 수 있는 무게는 i번째 로프 무게 * i가 될 것이다. 이것이 모두 내림차순으로 정렬이 되어 있어 가능하다.
for i in range(N):
result.append(ropes[i]*(i+1))따라서 정렬 후 로프를 i개 뽑는 경우를 결과 리스트에 넣어 최댓값을 출력하면 된다.
🔡 코드
import sys
input = sys.stdin.readline
N = int(input())
ropes = sorted([int(input()) for _ in range(N)], reverse = True)
result = []
for i in range(N):
result.append(ropes[i]*(i+1))
print(max(result))정렬을 위해 입력과 동시에 sorted() 메소드를 활용해 정렬된 리스트로 받도록 하였고, reverse 인자를 통해 내림차순으로 정렬하였다.
