[백준 2217] 로프 - python

2217번: 로프 (acmicpc.net)

2217번: 로프

'

문제풀이

처음 풀이

• 임의의 몇개의 로프들을 골라 최대 중량을 구하는 문제이므로 처음에 조합을 생각해냄
• 일단 최대값을 구하기 위해 lst값을 오름차순 해주었음
• 조합을 이용해 1개묶음, 2개묶음... n개묶음 까지 구한 후에 combi값에서 가장 큰 값들로만 이루어진 combi[0]에서 최소값 x 로프 개수(k)를 해주었음
• 하지만 메모리 초과가 떠서 실패,,

from itertools import combinations

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

combi = []
result = []
lst.sort(reverse=True)
for i in range(1, n+1):
    value = 0
    combi = list(combinations(lst, i))[:1]
    # print(combi)
    value = min(combi[0]) * i
    result.append(value)

result.sort(reverse=True)
print(result[0])

 

최종 풀이

• 위의 조합을 살펴보면 lst가 [15, 10, 5] 라면 (15), (10), (5), (15, 10), (10, 5), (15, 5), (15, 10, 5)로 묶이는걸 확인할 수 있는데 로프개수가 1개 묶음일땐 (15)가 최대, 2개 묶음일땐 (15, 10) 중 10*2가 최대, 3개 묶음일 땐 (15, 10, 5)에서 5 * 3이 최대값인걸 알 수 있다
• 조합을 이용하지 않아도 오름차순만을 이용해 현재 위치(n) * 로프개수(k=n+1)를 하여 최대값을 구할 수 있다는걸 찾아냄
• 공식 = rope[n] * (n+1)

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

rope.sort(reverse=True)

for i in range(n):
    result.append(rope[i]*(i+1))

print(max(result))