[백준 - Python] 2839번 : 설탕 배달

 

 

🌱   문제

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

💡   설명

해당 문제는 다이나믹 프로그래밍 또는 그리디 알고리즘을 요구하는 문제입니다.

우선 다이나믹 프로그래밍으로 풀이가 가능한지 확인하기 위해서는 2가지 조건이 있습니다.

1. 최적 부분 구조 (Optimal substructure)

2. 중복 부분 문제 (Overlapping subproblems)

즉, 큰 문제 상황을 작게 나누어서 해결하고자 할 때, 중복되는 상황이 발생 하며, 작게 나눠진 문제를 바탕으로 큰 문제를 해결할 수 있는가를 생각해보아야 합니다.

 

우선 설탕이 3kg 또는 5kg인 경우, 각각 1개의 봉지만 가져가도 참이 되는 가장 작은 문제상황입니다.

그렇다면 그 다음으로 큰 숫자인 6kg을 가져가려면 어떻게 해야 할까요?

3kg + 3kg 으로 6kg를 만드는 것입니다.

여기서 알 수 있는 사실은 6kg(큰 문제)를 2개의 3kg(중복 부분 문제) 으로 나누어 생각해볼 수 있다는 점입니다.

또한 각각의 부분 문제들이 3kg(1회)로 최적의 해(최적 부분 구조)를 가지고 있습니다.

아래 풀이는 다이나믹 프로그래밍 으로 해결한 소스코드입니다.

 

✏️   소스코드

#-*- coding:utf-8 -*-
import sys
INF = sys.maxsize

input = sys.stdin.readline
MIS = lambda: map(int, input().rstrip().split())

n = int(input())

# iKG에 대한 최소 배달 횟수를 기록
# n의 범위는 3 ~ 5000 사이
dp = [INF] * (5001)

# 만들어질 수 없는 경우에 대해서는 무한값으로 초기화
# 최소 상황에 대해 미리 초기화
dp[3], dp[4], dp[5] = (1, INF, 1)

# iKG을 배달하는 횟수 =
# iKG의 기존 배달 횟수와, (i-3)KG 또는 (i-5)KG에서 1회를 더하여 최소 값으로 재할당
for i in range(6, n+1):
    dp[i] = min(dp[i], dp[i-3] + 1, dp[i-5] + 1)

# 배달할 수 없는 경우는 INF 값이 변하지 않으므로 -1
# 배달 가능한 경우에는 최소 배달 횟수를 출력
print(dp[n]) if dp[n] != INF else print(-1)

 

 

 

github : https://github.com/tmdgh1592

tmdgh1592 - Overview