[Greedy] 2217번 - 로프(33일차)

#코드 실행 시간 단축
import sys
input = sys.stdin.readline
#로프의 개수 입력
n = int(input())
#로프의 중량 최대값 저장을 위한 list
rope = [0 for _ in range(n)]
#로프의 중량 최대값 저장
for i in range(n):
    rope[i] = int(input())

#사용된 로프의 개수를 세는 변수
rope_cnt = 1
#중량 최대값을 저장하는 변수
weight = 0
#내림차순 정렬된 각 로프에 대해서
for j in sorted(rope, reverse=True):
    #해당 로프 중량 최대값 x 총 로프 개수가 중량 최대값보다 크면 중량값 업데이트
    if(j*rope_cnt >= weight):
        weight = j*rope_cnt
    #사용된 로프의 개수 추가
    rope_cnt += 1
#저장된 중량 최대값 출력
print(weight)

#인사이트
#귀납적 접근으로 쉽게 풀이할 수 있었던 문제
#동전 지불하기 문제처럼 가장 작은 값을 기준으로 중량을 계산하는 greedy 접근이 필요했음
#n번째 로프에서 중량값이 업데이트되지 않더라도 그 이후에 업데이트가 가능하므로
#섣부른 for문 break는 지양하기