첫 그리디 문제.

1. 내 풀이: 시간초과

import sys 
from itertools import permutations
input = sys.stdin.readline

n = int(input())
people = list(map(int, input().split()))

minSum = float('inf')
Sum = 0
cantidate = [0] * 5
for perm in permutations(people, 5):
    for i in range(len(perm)):
        cantidate[i] = perm[i] + sum(perm[:i])
    Sum = sum(cantidate)
    minSum = min(Sum, minSum)

print(minSum)

답은 나오지만 시간초과 나오는 풀이 ... 지금보면 당연히 그렇다. permutation으로 모든 경우의 수를 다 체크해줬으니 말이다 ^^

2. 다른 풀이

import sys
input = sys.stdin.readline

n = int(input())
people = sorted(list(map(int, input().split())))
Sum = 0
for i in range(n):
    for j in range(i+1):
        Sum += people[j]
print(Sum)

풀이 출처: https://pacific-ocean.tistory.com/227

변수명 등이 조금 다르긴 하지만, 그래도 전체적인 로직은 똑같다. 어떻게 해야 합이 제일 작아지는지 생각을 해보고 구현을 하면 된다!

그리디 알고리즘 ? 🧐

이 블로그에서 참고!

알고리즘의 포인트는 다음과 같다.

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미
• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력 요구

3. 마치며

무턱대고 브루트포스로 풀었다가 ㅎㅂㅎ... 앞으로는 그리디도 마스터 해보자!