Baekjoon 문제 풀기 (2839번 : 설탕 배달) Python

2839번 : 설탕 배달

1. 문제읽기

---

dp 알고리즘? greedy 알고리즘?

처음에 몫, 나머지로 문제를 풀어보려고 했는데 경우의 수가 너무 많이 나와서 어려웠다.
그래서 다른 방법이 없을까 하다가 그리디 알고리즘을 떠올리고 문제를 풀려고 했는데, 5와 3이 겹치지 않아서 어려웠다… 또 포기
알고보니 그리디가 몫과 나머지로 푸는 코드인 것 같다.
다이나믹 프로그래밍이 되길래 또 도전했는데… 나에겐 너무 어려운 문제였나보다!!!

2. 제출 코드

---

다이나믹 프로그래밍 알고리즘과 그리디 알고리즘 방법 모두 정리해본다.

1) 다이나믹 프로그래밍 알고리즘 풀이

min함수를 써야하므로 INF 무한대 수를 만들어주고 반복문을 돌려서 값을 찾아낸다.
DP 알고리즘이 사실 점화식만 찾으면 나머지는 쉬운데..
점화식 찾는 건 정말 많은 연습이 필요할 것 같다.

INF = int(1e9)
n = int(input())

d = [INF] * 5001
d[3] = 1
d[5] = 1
for i in range(3, n+1):
    d[i] = min(d[i], d[i-3] + 1, d[i-5]+1)

if d[n] == INF:
    print(-1)
else:
    print(d[n])

2) 그리디 알고리즘 풀이

n이 5의 배수일 때, 5kg 봉지에 넣는 것이 무조건 best 다.
그렇지 않다면, 3kg 봉지에 하나씩 담는데, 5의 배수가 될 때 모든 설탕을 다시 5kg 봉지에 담으면 되므로 아래와 같이 간단하게 나타낼 수 있다.

n=int(input())
bag=0

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

3. 공부할 것

---

점화식을 알아내려면 우선 dp 테이블을 쭉 나열해서 써보고, 규칙을 찾는 것이 가장 중요한 것 같다.
나는 고작 11? 까지만 쓰고 규칙을 찾으려고 했는데, 그래서 더 어려웠다.
몫과 나머지를 처음부터 생각하긴 했지만 3을 빼주면서 5의 배수를 만드는 것은 생각도 못했다.
내일 푸는 문제는 더 열심히 고민해봐야지!!!

나는 초기화에 0을 많이 쓰는데, min함수를 써야해서 코드 짜기가 굉장히 어려웠었다.
5001을 넣어서 풀어보려고 시도해봤지만, 1e9를 써서 무한에 가까운 큰 수를 만드는 방법이 있었다는 것을 배웠다.
앞으로 큰 수 초기화를 시킬 때 써먹어봐야겠다.