문제 링크 (opens new window)

풀이

1. DP, 완탐시 2^5000시간
2. N그램 설탕을 가져가는 경우는 N-3그램 설탕을 챙긴 경우, N-5그램 설탕을 챙긴 경우까지의 최솟값 + 1에 해당한다.
3. 만약 N-3, N-5그램 경우 둘다 챙겨갈 수 없는 경우 Int.max로 사용

import Foundation

let N = Int(readLine()!)!
var dp: [Int] = .init(repeating: Int.max, count: 5004)

dp[3] = 1
dp[4] = Int.max
dp[5] = 1
dp[6] = 2
dp[7] = Int.max

if N < 8 {
    print(dp[N] == Int.max ? -1 : dp[N])
    exit(0)
}

for i in 8...N {
    if dp[i-3] == Int.max && dp[i-5] == Int.max {
        continue
    } else if dp[i-3] == Int.max {
        dp[i] = dp[i-5] + 1
    } else if dp[i-5] == Int.max {
        dp[i] = dp[i-3] + 1
    } else {
        dp[i] = min(dp[i-3] + 1, dp[i-5] + 1)
    }
}

print(dp[N] == Int.max ? -1 : dp[N])