[Python] 백준 2839 설탕 배달

 

문제 분석

• 3, 5kg 의 설탕
• 정확하게 N kg을 배달해야 한다.
• 최대한 적은 봉지를 들고 가려고 한다.
• 정확하게 만들 수 없다면 -1 출력

 

코드 설계

• 순서가 없고, 중복을 허용하는 중복 순열 : combinations_with_replacement
• 최대 n // 3 + 1개까지 뽑을 수 있다고 가정할 때 (3으로 딱 떨어지지 않을 수도 있으니 +1)
• 3,5의 조합으로 만들 수 있는 N을 찾고 그 중 최소로 뽑은 경우를 찾는데..
• 뽑는 개수는 점점 늘어갈 것
• 즉 처음 만족하는 경우가 최소의 개수로 뽑는 경우
• 만약 찾으면 더 이상 찾지 않고 종료
• or 끝까지 찾지 못하면 -1 출력

 

정답 코드

import sys
input = sys.stdin.readline
from itertools import combinations_with_replacement, combinations

n = int(input())
iter = [3, 5]
max_sugar = n//3 + 1

for sugar in range(1, max_sugar+1) :
    for k in combinations_with_replacement(iter, sugar) :
        if sum(k) == n :
            print(len(k))
            sys.exit(0)
print(-1)

 

다른 정답 코드 1 : https://ooyoung.tistory.com/81

sugar = int(input())
  
bag = 0
while sugar >= 0:
    if sugar % 5 == 0: # 5의 배수이면
        bag += (sugar//5)
        print(bag)
        break
    sugar -= 3
    bag += 1 # 5의 배수가 될때까지 설탕 -3, 봉지 -1
    
# 루프가 자연적으로 끝나는 경우 실행
else :
    print(-1)

 

다른 정답 코드 2 : 

1. 그리디

n = int(input())
cnt = 0

while True:
    if n % 5 != 0:
        n = n - 3
        cnt += 1

    elif n % 5 == 0:
        cnt += n // 5
        print(cnt)
        break

    if n < 0:
        print(-1)
        break

 

2. DP

x = int(input())
dp = [-1] * (x + 1)

if x >= 3:
    dp[3] = 1
if x >= 5:
    dp[5] = 1

for i in range(6, x + 1):
    if dp[i - 3] < 0 and dp[i - 5] < 0:
        dp[i] = -1

    elif dp[i - 3] > 0 and dp[i - 5] > 0:
        dp[i] = 1 + min(dp[i - 3], dp[i - 5])

    else:
        dp[i] = 1 + max(dp[i - 3], dp[i - 5])

print(dp[x])