[백준] 2839 설탕 배달 [Python] 동적계획법

 

www.acmicpc.net/problem/2839

2839번: 설탕 배달

문제

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

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

---

이 문제를 읽고 떠오른 방법은 다이나믹 프로그래밍을 사용하는 것과 그리디 알고리즘을 사용하는 것.

먼저 동적 계획법을 사용해서 푸는 것이 개인적으로 편하기 때문에 먼저 다이내믹 프로그래밍을 이용하여 풀어보았다.

---

kg = int(input())

lut = [-1 for i in range(kg+1)]
for i in range(kg+1):
    if i < 3 or i == 4: continue
    if i == 3 or i == 5: lut[i] = 1
    elif lut[i-3] == -1 and lut[i-5] == -1: continue
    elif lut[i-3] == -1: lut[i] = lut[i-5] + 1
    elif lut[i-5] == -1: lut[i] = lut[i-3] + 1
    else: lut[i] = min(lut[i-5], lut[i-3]) + 1

print(lut[kg])

---

이번 문제 같은 경우 3 kg 봉지와 5 kg 봉지를 사용하여 주어진 킬로그램을 배달할 때, 가장 옵티멀 한 봉지 개수를 찾아내야 한다. 3kg과 5kg을 이용했을 때, n kg만큼 딱 떨어지는 만큼 담을 수 없다면 -1을 프린트한다. dp는 프로그램이 중복된 계산을 하는 것을 피할 때 쓰는 방법 중 하나로, formula를 세워 중복 계산을 피하는데, 이 문제는 (n-3) kg을 배달할 때 사용한 봉지의 개수와 (n-5) kg을 배달할 때 사용한 봉지의 개수 중 적게 사용한 kg에서 1을 더해주는 경우를 생각하면 된다. 따라서 (n) kg = min((n-3) kg, (n-5) kg) + 1이라는 함수가 세워졌다.

 

이제 베이스 케이스를 세워야 한다. 작은 케이스부터 생각을 해보자. 3kg보다 작은 kg이 주어진다면, 딱 떨어지게끔 담을 수 없으므로 -1을 프린트한다. 4kg이 주어졌을 때 역시 3kg을 사용하고 나면 1kg이 남으므로 -1이 나온다. 이런 식으로 베이스 케이스를 세워본다면,

1) n < 3: -1

2) n = 3: 1

3) n = 4: -1

4) n = 5: 1

이렇게 된다. n = 6인 경우를 보자. 6kg = min(1 when 3kg, -1 when 1kg)이 나온다. 이때 -1은 해당 킬로그램은 배달이 불가하다는 것이므로 -1가 아닌 수를 골라 +1을 시켜준다. 따라서 6kg을 배달할 때 2개의 봉지가 사용된다.  7kg의 경우 4kg과 2kg 모두 -1을 가진 값이므로 -1이 나온다. n = 8, 8kg = min(1 when 5 kg, 1 when 3 kg) + 1 이므로 역시 2개의 봉지를 사용한다. 

위의 코딩의 경우 rumtime O(n) space O(n)이 나온다. Space를 줄일 수 있는 방법은 없을까? 

---

kg = int(input())

lut = [-1 for i in range(6)]
for i in range(kg+1):
    if i < 3 or i == 4: continue
    idx, three, five = i%6, (i-3)%6, (i-5)%6
    if i == 3 or i == 5: lut[idx] = 1
    elif lut[three] == -1 and lut[five] == -1: continue
    elif lut[three] == -1: lut[idx] = lut[five] + 1
    elif lut[five] == -1: lut[idx] = lut[three] + 1
    else: lut[idx] = min(lut[five], lut[three]) + 1

print(lut[kg%6])

---

코드를 자세히 보면 알겠지만, 각 kg마다 필요한  봉지 개수를 저장해놓은 배열은 굳이 n개가 필요하지 않다. lut [i] = min(lut [i-5], lut [i-3]) + 1 즉, 내가 액세스를 해야 하는 어레이는, 현재 위치에서 최대 -5 만큼이다. 그러면 0부터 5까지의 element만 있으면 space 사용량을 O(n)에서 constant, 즉 O(1)으로 줄일 수 있다.