[Python] 백준 2217번 - 로프

2217번: 로프

 

문제

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

 

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

 

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

 

입력

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

 

출력

첫째 줄에 답을 출력한다.

 

import sys
input = sys.stdin.readline

n = int(input())
rope = []
for _ in range(n):
    rope.append(int(input()))

rope.sort(reverse = True)
for i in range(n):
    rope[i] *= i + 1

print(max(rope))

이 문제는 설명이나 테스트 케이스가 한 개밖에 없어서 문제를 제대로 이해 못했습니다. (저만 그런 것일수도,,,) 아무튼 문제를 이해하기 위해 질문 게시판을 가보니 정답이나 다름없는 힌트를 주신 분이 계셔서 그걸 보고 풀었습니다. ㅠㅠ 제 능력으로 푼게 아니라 많이 아쉽네요..

 

- 위에 가셔서 문제 부분에 줄쳐놓은 곳을 보시면 저는 이 부분을 로프 여러 개의 조합으로 풀라는 말로 잘못 이해했습니다.

- 알고보니 입력된 로프를 내림차순으로 정렬하여 최대 사용할 수 있는 개수를 n개로 생각하는 것이었습니다.

- 그렇게 된다면 입력받은 로프를 내림차순으로 받은 후 앞에서부터 1, 2, ... ,n개까지 곱해주고 그 중에서 가장 큰 수가 최대 중량(답)이 됩니다. 그 이유는 각 자리마다 들 수 있는 최대 중량이 다르기 때문인데요. 로프를 n개 사용하려면 가장 작은 숫자를 기준으로 최대 중량을 설정해야 하고 로프를 1개만 사용하기 위해서는 입력받은 수 중에서 가장 큰 수를 골라야 합니다. 그래서 자릿수마다 한 개씩 늘리는 것이죠.

- 예시

#입력
5
20
4
30
10
5

 

- 위와 같은 입력시 내림차순으로 정렬하면 [30, 20, 10, 5, 4]가 됩니다. 그렇다면 로프 하나만을 사용해서 들 수 있는 최대 중량은 무엇일까요? 당연히 30이겠죠? 저 중에서 가장 큰 수이니까요. 그렇다면 로프 두 개를 사용한다고 가정했을 때는 30과 20이 됩니다. 그 이유는 30의 경우 20의 최대 중량을 나눠서 들 수 있기 때문인데요. 나머지 10, 5, 4 중에서 두 개를 사용하게 되면 최대 중량을 구할 수 없습니다. 그렇기 때문에 앞에서부터 순차적으로 1부터 n까지 곱해 개수를 맞춘 것이죠. 

- [30, 40, 30, 20, 20]으로 각 자리마다 1부터 5까지 곱한 수 중에서 최댓값인 40을 최대 중량으로 볼 수 있습니다.

 

#출력결과
40

 

설명을 저만 못알아듣는 것인지... 살짝 우울해지는 문제였습니다.🥲

 

피드백은 언제나 환영합니다.