문제
N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.
하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.
각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.
▶️ 입력 조건
- 첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.
▶️ 출력 조건
- 첫째 줄에 답을 출력한다.
풀이
해당 문제는 코드를 작성하는 시간보다 문제를 어떻게 풀지 고민하는 시간이 더 오래걸렸다.
(오답을 2번 정도 받았음...)
처음에는 가장 낮은 무게의 로프에 맞춰서 N 만큼 곱해주면 된다고 생각했다.
따라서 예제의 정답이 20이 나온 이유도 10 * 2 = 20 이라고 생각했다.
그러나 추가로 예제를 만들어보니 내 방법이 잘못되었다는 것을 인지했다.
예를 들어 로프가 5개 있는데 각 무게는 2, 4, 7, 9, 10 있다고 가정해보겠다.
중요한 포인트는 "임의로 몇 개의 로프를 골라서 사용해도 된다" 라는 조건이다.
그렇다면 가장 무게가 높은 로프부터 (무게가 높은 로프가 낮은 로프보다 무거운 짐을 들 확률이 높다고 생각했음) 작은 로프 순으로 하나씩 꺼내보며 들 수 있는 최대 중량을 구해보겠다.
중량을 계산하는 공식은 가장 낮은 무게 * 총 로프 개수
- 10 뽑았다고 가정 -> 10 * 1 = 10
- 10, 9 뽑았다고 가정 -> 9 * 2 = 18
- 10, 9, 7 뽑았다고 가정 -> 7 * 3 = 21
- 10, 9, 7, 4 뽑았다고 가정 -> 4 * 4 = 16
- 10, 9, 7, 4, 2 뽑았다고 가정 -> 2 * 5 = 10
이렇듯 3개를 뽑았을 경우가 가장 높은 무게를 들 수 있다.
이를 토대로 고안해낸 방법은 모든 경우의 수를 저장해두고 가장 높은 무게를 출력하는 방식으로 구현했다.
n = int(input())
ropes = []
for _ in range(n):
ropes.append(int(input()))
ropes.sort(reverse=True)
count = 1
weight_list = []
for rope in ropes:
weight_list.append(rope * count)
count += 1
print((max(weight_list)))
'Algorithm > Problem Solving' 카테고리의 다른 글
[Beakjoon] 2437 : 저울 - python (1) | 2025.01.24 |
---|---|
[이코테] 왕실의 나이트 - python (0) | 2025.01.24 |
[Beakjoon] 1026 : 보물 - python (0) | 2025.01.24 |
[Beakjoon] 1343 : 폴리오미노 - python (0) | 2025.01.24 |
[Baekjoon] 11047 : 동전 0 - python (0) | 2025.01.23 |