[BOJ] 백준 2217 로프 (Python) + enumerate

문제

2217번: 로프

 

문제 해석

접근 방법

그리디 알고리즘과 정렬을 통해 풀 수 있는 문제입니다. 로프 n개를 선택했을 때 버틸 수 있는 최대 중량을 각각 계산한 후 그 중 가장 높은 값 선택하면 됩니다.

 

풀이 과정

각 로프의 최대 중량과 로프 조합의 최대 중량을 구분하기 위해 각 로프의 최대 중량은 로프의 내구도라고 표현하겠습니다.

로프 n개를 선택했을 때 버틸 수 있는 최대 중량은 n개 중 가장 약한 로프의 내구도 * n 입니다.

 

만약 주어진 로프가 다음과 같다면 로프 n개를 선택했을 때 버틸 수 있는 최대 중량은 다음과 같습니다.

 ex) 100, 80, 50, 20

• 로프 1개일 때 : 100을 선택하면 100*1 = 100의 중량을 버틸 수 있음
• 로프 2개일 때 : 100, 80을 선택하면 80*2 = 160의 중량을 버틸 수 있음
• 로프 3개일 때 : 100, 80, 50을 선택하면 50*3 = 150의 중량을 버틸 수 있음
• 로프 4개일 때 : 100, 80, 50, 20을 선택하면 20*4 = 80의 중량을 버틸 수 있음

 

따라서 해당 로프의 조합으로 버틸 수 있는 최대 중량은 160입니다.

 

 

위 예시처럼 내구도가 높은 로프부터 정렬한 후, 로프를 순서대로 추가해 개수를 늘려가며 최대 중량을 계산을 할 수 있습니다. 이번 문제에서는 로프의 내구도과 인덱스를 함께 사용하기 위해 enumerate로 배열을 재구성했습니다.

 

• enumerate() : iterable 객체(list, str, range, tuple 등)를 인자로 받아서 인덱스와 원소로 이루어진 튜플을 반환하는 함수

arr = ["A", "B", "C"]

# enumerate()로 생성된 튜플의 원소를 idx, val에 할당받음 (순서대로 인덱스, 값)
for idx, val in enumerate(arr):
	print(idx, val)

# 0 A
# 1 B
# 2 C

 

전체 코드

from sys import stdin

N = int(stdin.readline().rstrip())
ropes = [int(stdin.readline().rstrip()) for _ in range(N)]
ropes.sort(reverse=True)

# n개 (idx+1개)의 로프를 사용할 때 들 수 있는 최대 하중을 담은 배열
ropes = [(idx+1)*r for idx, r in enumerate(ropes)]

print(max(ropes))