[백준]2217-그리디(로프)

문제풀이

문제 https://www.acmicpc.net/problem/2217

1. 인풋을 받고 오름차순으로 리스트에 정렬시킨다

n = int(input())
rope = []

for i in range(n):
    rope.append(int(input()))
    
rope.sort()

2. 문제를 잘 읽어보면 모든 로프를 사용하지 않아도 된다고 했다. 이것이 이 문제의 키포인트이다.
   예를 들어 rope[10, 15, 20, 30]이라면 경우의 수는 4가지이다.

• 10 * 4 = 40kg
• 15 * 3 = 45kg
• 20 * 2 = 40kg
• 30 * 1 = 30kg

3. 위의 예시를 이용해 코드를 구현하면 이렇게 된다. 최대 무게를 구해야 하므로 오름차순으로 정렬하고 [-1]값을 프린트해준다.

weight = []

for i in range(n):
    w = rope[i]*(n-i)
    weight.append(w)
weight.sort()

print(weight[-1])

마무리

• 어제 문제는 풀었지만 깜빡하고 제출하진 못했다. 매일매일 꾸준히 열심히 해야겠다.
• 알고리즘 문제를 풀 때 연습장에다 펜으로 알고리즘을 분석하면서 예시를 직접 만들고 해보니 이해가 더 쉽고 잘되었다. 예시 여러 개를 직접 만들어 보는 것이 중요한 것 같다.