설탕 배달 (파이썬)

이코테에서 효율적인 화폐 구성 문제와 비슷해서 비슷한 풀이로 풀 수 있었다.

첫번째 코드

n = int(input())
#설탕이 최대 5000이므로 
data = [5001] * (n+1)
bag = [3, 5]

for i in bag:
  if i > n:
    continue
  data[i] = 1

#배열 n에...3키로,, 5키로
for k in bag:
  for i in range(k, n+1):
    if data[i-k] != 5001: #가방 단위로 배달 가능하면...
      data[i] = min(data[i], data[i-k]+1)

if data[n] != 5001:
  print(data[n])
else:
  print(-1)

 

이전에 이 문제를 푼 코드가 있어서 확인해 봤더니 이전에 푼 코드가 더 빠르고 간단했다...

 

이전에 푼 코드

1. 3으로만 가능한 배달

2. 5와 3으로 가능한 배달

3. 5와 3 둘다 불가능한 배달

으로 나눌 수 있는데, 먼저 3으로만 가능한 배달은 n이 3, 6, 9, 12이다. 13이후로는 5와 3을 사용하여 배달이 가능하므로 5를 사용해야한다

 

코드

n = int(input())
count = 0
while(n != 0):
  if n == 3 or n == 6 or n == 9 or n == 12:
      count += n//3
      break
  elif n < 3:
    count = -1
    break
  n -= 5
  count += 1

print(count)