[DP] 2839번 - 설탕배달 - 실버4

[heerucan]

n = int(input())

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


for i in range(6, 5001):
    if i % 5 == 0:
        d[i] = d[i-5] + 1
    elif i % 3 == 0:
        d[i] = d[i-3] + 1
    elif d[i-3] > 0 and d[i-5] > 0:
        d[i] = min(d[i-3], d[i-5]) + 1

print(d[n])

왜 점화식이 저렇게 나오지?

• 와 찬찬히 보니까 이제 알 것 같은데 1로 만들기 문제와 같은 맥락이다. 진짜 머리를 왜 달고 다니지?

1. 5로 나눠진다면, 어떤 숫자를 i라고 보면 5로 나눠떨어지니까 한 단계 전이 5로 값을 빼준 것과 같다. 긍까 15는 5로 나눠떨어지니까 15까지의 연산은 D[15]이고, 그 전까지는 10인데 10까지의 연산은 D[10]이다. 글구 10에서 15로 가는 과정에서 연산은 1번 필요해서 +1을 해준다. 그래서 점화식이 d[i] = d[i-5] + 1이 된다.

2. 3으로 나눠 떨어지는 것도 마찬가지다.
   예를 들어, 9를 보면 9까지의 연산을 위해 필요한 연산횟수는 D[9]이고, 그 전단계인 6을 위한 연산횟수는 D[6]이다. 그리고 6에서 9로 가기 위해 필요한 연산은 1번이기에 이 점화식 또한 d[i] = d[i-3] + 1이 된다.

3. 마지막으로 11과 14와 같이 처음부터 3, 5로 나눠 떨어지지 않지만 3 또는 5를 빼고 난 후 나눠 떨어지는 경우에는 최솟값을 구하면 된다.

4. -1을 계산할 필요는 없다... 초기에 -1 배열을 만들면 되니까...

결론적으로 난 바보다..

모르겠음

• 아 점화식을 전혀 모르겠었다. 문제가 쉽다고 생각했는데 어떻게 접근해야 하는지 모르겠다.
• 처음에 풀이한 방법은 아래와 같다. 문제는 11 케이스가 안된다.. 아 진짜 안 풀려서 맥북 뽀개버릴뻔;; 아 인성터질 거 같다.