[백준/Swift] 2839번: 설탕 배달

 

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

2839번: 설탕 배달

 

이 문제는 DP 또는 Greedy로 풀 수 있는데, DP 연습을 하고 있기 때문에 DP로 풀어봤다!

우선, 차분히 예제를 두고 쭉 적어봤다. 규칙을 찾아야 하기 때문!

- 3의 배수

- 5의 배수

- 3와 5의 합으로 나올 수 있는 수

 

그런데 쭉 숫자들을 적어 내리다 보니, 8(3+5) 이후로는 3과 5로 모두 나타낼 수 있었다!

그래서, 초기값을 3, 5, 6으로만 주고 8 이후로 작은 문제의 답으로 큰 문제의 답을 내는 dp를 구현했다.

8 이후의 수는 이전 값에 3을 더한 값 / 이전 값에 5를 더한 값 으로 나뉘기 때문에 

min(dp[i-3], dp[i-5]) + 1로 했다.

여기서 더 추가할 것은, dp[i-5]가 0일 수도 있다는 것이다! dp[12]의 경우, dp[12-5] = dp[7] = 0 이므로 이 부분을 꼭 생각해야 한다.

 

import Foundation

//input
let n = Int(readLine()!)!
var dp = [Int](repeating: 0, count: 5001)
dp[3] = 1
dp[5] = 1
dp[6] = 2
if n >= 8 {
    for i in 8...n {
        dp[i] = min(dp[i-3] == 0 ? n+1 : dp[i-3], dp[i-5] == 0 ? n+1 : dp[i-5]) + 1
    }
}
print(dp[n] == 0 ? -1 : dp[n])

 

dp는 어려운데 재미있다...! 규칙 찾아내기~~