백준 2839번: 설탕배달 (Dynamic Programming)

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

2839번: 설탕 배달

 

 

 

 

1. 코드

import sys

box = [-1]*5001
box[3] = 1
box[5] = 1

n = int(sys.stdin.readline())

for i in range(6,n+1):
    if box[i-3] != -1:
        box[i] = box[i-3] + 1
    if box[i-5] != -1:
        box[i] = box[i-5] + 1

print(box[n])

 

처음에 틀린 이유는 if 문에서 if i%3 == 0 과 같은 방식으로 3과 5로 나누어 떨어지는가에 대해서 접근하려고 했기 때문이다. 8, 11, 13같은 5 혹은 3 만으로 나누어 떨어지지 않는 값에 대해서 처리해야 하므로 이과 같은 방식으로 구현하면 된다. min() 함수를 사용하지 않아도 되는 이유는 5에 대해 접근하는 if 문을 가장 아래에 적어주어서이다. 무겁지 않은 배달을 위해서는 최대한 5를 많이 써야한다.

 

 

2. 더 짧은 코드 

import sys

cnt = 0
n = int(sys.stdin.readline())

while True:
    if n%5 == 0:
        cnt += n//5
        break
    else:
        n-=3
        cnt+=1
    if n<0:
        print(-1)
        break
if n>=0:
    print(cnt)

동적 프로그래밍 구현 없이 while문을 사용한다.