[python/파이썬] 백준 2217 로프

문제

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입력 1 복사

2
10
15

예제 출력 1 복사

20

 

 

[소스 코드]

 

N개의 로프를 사용한다고 했을 때 가장 '작은 중량을 버티는 로프의 중량 * N'가  최대 중량임은 바로 알았다.

하지만 많은 로프를 사용한다고 해서 가장 큰 중량을 버틸 수 있는 것이 아님에도 처음에 짠 코드는 모든 로프를 사용하는 방향으로 작성되었다.

모든 로프를 사용하지 않아도 된다는 조건을 무시한 탓에 깊게 생각하지 못한 것 같다.

아무리 많은 로프를 사용한다고 해도 가장 적은 중량을 버티는 로프가 제일 중요하기에 그 값이 터무니없이 작다면 여러 개의 로프를 사용하는 것이 단순히 몇 개의 로프를 사용하는 것보다 더 좋지 않은 결과가 나타난다.

 

따라서 weight 리스트에 로프를 1개 사용했을 때, 2개 사용했을 때...이렇게 경우를 나누어서 모두 저장하고,

max값을 찾아서 출력하였다.

가장 큰 중량값을 찾아야 하기에 1개를 사용했을 때 가장 큰 값이 나오려면 최댓값을 가지는 로프를 사용해야 하고, 2개일 때는 첫 번째로 큰 로프와 두 번째로 큰 로프를 사용해야 한다. 이런 식으로 weight값을 저장하기 위해서는

rope의 값을 내림차순으로 저장하고 각 중량 값과 로프의 개수를 곱해서 weight에 저장한다.

n = int(input()) # 로프의 개수 n
rope = [] # 각 로프의 들 수 있는 중량
weight = [] # 로프들을 사용했을 때 들 수 있는 중량

for i in range(n): # 로프가 들 수 있는 중량을 저장
    x = int(input())
    rope.append(x)
    
rope.sort(reverse=True) #rope를 내림차순으로 정렬
for i in range(n):
    weight.append((i+1)*rope[i]) 
    # 첫번쨰 중량(최대값)과는 1, 그 다음은 2...이렇게 곱해서 저장
    # 로프를 n개 사용한다고 했을 때 각 로프에 걸리는 중량은 가장 적은 중량을 들 수 있는 로프의 중량
    # ex) 로프 10 15 20을 모두 사용할 때 각 로프에는 중량이 최대 10 걸릴 수 있음(로프에 모두 고르게 중량이 걸리기 때문)
	# 따라서 로프 사용 개수에 따른 중량을 계산해 최대값을 구하고자 함
    
print(max(weight))