[백준]2217번 로프 - 그리디

 

n = int(input())

weight = []
for i in range(n):
    weight.append(int(input()))
weight.sort(reverse=True)
max = weight[0]
for i in range(1, n):
    if max < weight[i] * (i+1):
        max = weight[i] * (i+1)

print(max)

 

코드 설명

각 무게를 weight 리스트에 입력 받은 후 내림차순으로 정렬한다. 현재까지 가장 큰 값은 weight[0] 이다.

반복문을 수행하면서 weight[i] * (i+1) 의 값이 max 보다 크면 갱신하여 준다.

 

Point : 먼저 중량순으로 정렬해주기 위해 sort(reverse=True) 함수를 이용하여 준다. 맨 처음 최대 중량은 weight[0] 즉, 가장 많이 드는 로프 하나만 사용하는 것으로 설정해준다. 

반복문을 돌면서 로프 2개, 3개, 4개 ... 을 이용했을 때의 중량을 max와 비교하여 크다면 갱신시켜 주면 된다.

로프를 여러 개 이용할 경우 그 로프들 중 (최소 중량 * 갯수)가 최대 중량이 되므로 내림차순 정렬을 통해 큰 값부터 위치시켜 반복을 시켜주는 과정이 필요하다.