백준 2839 (설탕배달) 파이썬

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

2839번: 설탕 배달

이 문제는  DP(dynamic programmig)의 기초 문제라고 볼 수 있다. DP의 첫 걸음마를 떼는 나에게 좀 까다로운 문제였다.  우선 DP가 뭔지 부터 공부해야 했고 이론을 공부 후 실제 문제에 적용하려고 보니 쉽지 않았다. 그만큼 DP라는 유형이 쉬운 유형의 알고리즘은 아닌걸 알았다. 이 문제는 3kg이 1개일때, 2개일때, 3개일떄, n개일때를 생각하여 3kg의 갯수에 기준을 맞추고 그에 맞게 5kg의 갯수를 정해주는 방식으로 풀어야한다. 그리고 3kg이 1개일때, n개일때의 5kg의 개수를 더한값을 dp[]에 넣어주어 필요할때 써서 바로 찾을 수 있게 풀이를 해야 빠른 풀이가 가능하다. 바로 이런 방법이 다이나믹 프로그래밍이다. 아래는 내가 짠 코드이다.

 

import sys
N = int(sys.stdin.readline())
cnt =0
dp = []
for i in range(N):
    num3=3*i
    num=N-num3
    if(N==3 or N==5):
        dp.append(1)
        break
    if(N==4 or N==7):
        dp.append(-1)
        break
    if(num<0):
        break
    if(num%5==0):
        num5=num//5
        cnt=i+num5
        dp.append(cnt)
print(min(dp))

 

이 문제는 내가 짰지만 짜고 나서 문제를 통과했을때도 기분이 좋진 않았다 뭔가 맘에 들지 않은 코드인거 같아서이다. 정답에 맞추어 코드를 짠 느낌이랄까....? 그래서 찝찝한 기분이 들어 다른사람들의 풀이코드를 보았는데 확실히 내 코드가 아쉬워 보이는 코드인거 같은 느낌이 든다. 내 코드는 이런 방법도 있구나 정도로 알고 넘어가고 다른사람의 코드를 보는 걸 추천한다. (ㅠㅠ...열심히 풀었는데...)