Computer Science/Algorithm
[Baekjoon] DP - 2839 설탕 배달
ddu0422
2023. 9. 11. 16:14
문제
2839번: 설탕 배달
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그
www.acmicpc.net
풀이
"""
d[n]: n kg을 가져갈 설탕 봉지의 최소 개수
"""
n = int(input())
INF = 10**9 + 1
def solution(n):
d = [INF] * (n + 1)
for i in range(3, n + 1):
if not i % 3:
d[i] = min(d[i], i // 3)
if not i % 5:
d[i] = min(d[i], i // 5)
d[i] = min(d[i], d[i - 3] + 1, d[i - 5] + 1)
return d[n] if d[n] != INF else -1
print(solution(n))
채점 결과
