백준 2839 파이썬 - 설탕 배달 - 동적 계획법

백준 2839 파이썬

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

2839번: 설탕 배달

 N킬로그램의 설탕이 주어졌을 때, 설탕을 담기 위해 3키로그램과 5키로그램 봉지로 가장 적은 양의 봉지를 만들어 내는 방법을 구하는 문제이다. 이 문제는 계산 횟수를 줄이기 위해 이전에 계산했던 값을 기억해뒀다가 재사용하는 메모이제이션을 활용하는 것이 적당하다고 판단했습니다.

 

 

3 ~ N킬로그램까지 작은 숫자부터... 각각 가장 적은 양의 봉지를 저장해두면... 해당 값보다 3, 5 큰 위치에서 이전 값을 재사용할 수 있다.

 

Python 풀이

import sys

read = sys.stdin.readline
N = int(read())

arr = [5001] * (N+5)
arr[3] = arr[5] = 1

for i in range(6, N+1):
    arr[i] = min(arr[i-3], arr[i-5]) + 1

print(arr[N] if arr[N] < 5001 else -1)

• arr 배열은 N킬로그램일 때, 각각 가장 적은 양의 봉지를 담을 용도로 사용된다.
  • 최소 값 구해야하기 때문에 N의 범위보다 하나 큰 값이 "5001"을 값으로 지정한다. 
  • index 3, 5에는 각각 1개의 봉지를 사용하고 최초의 값으로 이용하기 위해 "1"을 대입한다.
  • 배열의 크기를 "N+5"로 잡은 이유는... N의 값이 5보다 작은 경우 Index Out of Range 오류를 잡기 위해서다.
• 배열이 5와 같거나 보다 작은 경우는 이미 결과가 저장되어있기 때문에 for문의 range는 6부터 시작한다.
  • 6부터는 해당 위치보다 "-3", "-5"의 위치 중 작은 값을 갖고와서 1을 더하면 해당 위치에서 가장 적은 양의 봉지를 구할 수 있다. 
• N킬로그램을 만들 수 없으면 arr배열값이 5000보다 크기 때문에 치환해서 -1을 반환한다.

 

반례

• 마지막 출력부분에서 arr[N] != 5001 이런식으로하면 반례가 발생한다.
  • N이 7인 경우... 7-3=4, 7-5=2 --> 2, 4 모두 5001이 기본값이기 때문에 5002가 답으로 반환될 수 있다.