[백준 2839] 파이썬 설탕 배달 문제 풀이

백준 2839번 문제 파이썬 설탕 배달 풀이 입니다.

파이썬 설탕 배달 문제 풀이

문제

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

문제 풀이 (정답 코드)

n = int(input())
INF = 10e7
dp = [INF] * (5001)
dp[3] = 1
dp[5] = 1

for i in range(1,n+1):
  dp[i] = min(dp[i], dp[i-3] + 1)
  dp[i] = min(dp[i], dp[i-5] + 1)

print(dp[n] if dp[n] != INF else -1)

평범한 DP 문제다. 실수했던 점은 처음 dp 테이블을 만들 때 0으로 초기화를 해서, min값을 저장할 때 자꾸 0이 나왔었다. INF값을 만들어서 INF값으로 초기화를 하니까 정상적으로 동작한다. 

 

맺으며

DP 문제는 공통적으로 어떤 상황일 때 그 상황의 최선의 값을 다시 사용하고 (반복 계산을 피하고) 리스트에 저장해둔다. 문제를 많이 풀어보면서 한 번에 DP유형임을 알아볼 수 있는 눈을 키워야겠다.