[다이나믹 프로그래밍 + 그리디] 백준 실버5 14916번: 거스름돈(Swift)

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

14916번: 거스름돈

문제풀이

위 문제는 거스름돈 5원과 2원으로 주어진 돈을 거슬러 줘야 하는데 이때 동전을 최소한으로 사용하여 거슬러 줘야 한다.

먼저, 15원까지 동전의 수를 나열해 보았다.

나열해 본 결과 반복되는 패턴이 있음을 알 수 있다.

주어진 돈이 5의 배수가 아니면 주어진 돈 n 원에 대한 동전의 개수는 n - 2원에 대한 동전의 개수 + 1인 것을 알 수 있었다.

때문에 위 문제는 다이내믹 프로그래밍을 활용하여 문제를 해결할 수 있다.

var n = Int(readLine()!)!
var result = 0

var dp = Array(repeating: 0, count: n + 1)

if n == 1 {
  print(-1)
} else if n == 2 {
  print(1)
} else if n == 3 {
  print(-1)
} else {
  dp[1] = -1
  dp[2] = 1
  dp[3] = -1
  
  for i in 4...n {
    if i % 5 == 0 {
      dp[i] = i / 5
      continue
    }
    dp[i] = dp[i-2] + 1
  }
  print(dp[n])
}

위 코드와 같이 n이 1 또는 3이 아닌 경우 돈을 거슬러 줄 수 있고,
n이 4 이상부터는 패턴이 적용되기 때문에 반복문을 통해 계산할 수 있다.