본문 바로가기
CS/알고리즘

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

by 마이자몽 🌻♚ 2021. 10. 5.

백준 2839 파이썬

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

 

2839번: 설탕 배달

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그

www.acmicpc.net

 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가 답으로 반환될 수 있다.

댓글0