[파이썬(Python)] 백준 2839번

그리디 알고리즘 문제라고 하는데.. 나는 아직 그게 뭔지 잘 모른다.

그냥 수학적으로 접근했다.

 

먼저, 제일 적은 양의 봉지를 쓴다면 어떤 상황이어야 할까?

최대한 많이 5kg 봉지를 써야한다.

그래서 최대한 5kg 봉지를 많이 썼을 때 5kg 봉지의 수를 구하고, 이후 N을 넘지 않는 선에서 3kg 봉지의 수를 하나씩 더해준다. 그리고 그 결과를 values 배열에 추가해주는 방식으로 답이 될 수 있는 값들을 모았다.

 

나는 가장 적은 봉지를 쓰는 경우의 수부터 배열에 담았기 때문에,

답을 구하는 과정에선 그냥 배열의 인덱스 순서대로 체크해주면 된다.

 

코딩하면서도 비효율적인 것 같다는 생각을 했는데.. 역시나 였던거 같다.

import math

N = int(input())

values = []

Min = math.floor(N/5)

for i in range(Min+1):
    j = 0
    while True:
        if (5*(Min-i) + 3*j) > N:
            break
        else:
            j += 1
    values.append((Min-i, j-1))

result = False
answer = 0
for e in values:
    if not result:
        if e[0]*5 + e[1]*3 == N:
            result = True
            answer = e[0]+e[1]

if result:
    print(answer)
else:
    print(-1)