Swift - 백준 2839번 설탕 배달 (다이나믹 프로그래밍 DP)

2839번 문제는 대표적인 다이나믹 프로그래밍(DP) 문제라고 할 수 있겠습니다

 

다이나믹 프로그래밍이란 이전에 풀어던 값을 한번 쓰고 버리는 것이 아닌 값을 저장하였다가 이후 값을 찾아내는데 있어서 또 사용하는 방식의 프로그래밍 방식입니다. 2839번 설탕 배달 문제도 마찬가지입니다.

 

문제 조건

• 봉지는 3kg 와 5kg 의 설탕을 담을 수 있는 봉지가 존재합니다.
• 최소한의 봉지로 원하는 설탕만큼을 배달해야 합니다.
• 정확하게 N 킬로그램을 만들 수 없다면 -1 을 출력합니다.

문제 해결

• 문제를 해결하기 위해서는 먼저 작은 숫자의 출력값부터 생각해봅니다.
• 1은 -1
• 2는 -1
• 3은 1, arr[3] = arr[3]
• 4는 -1
• 5는 1, arr[5] = arr[5]
• 6은 2, arr[6] = arr[3] + arr[3]
• 7은 -1
• 8은 2, arr[8] = arr[5] + arr[3]
• 9는 3, arr[9] = arr[6] + arr[3]

규칙을 찾아보면 arr[i-5] + arr[i-(i-5)] 또는 arr[i-3] + arr[i-(i-3)] 의 값이 arr[i]의 값으로 들어가는 것을 확인할 수 있습니다.

하지만 이 값들은 해당 arr[i-5] 와 arr[i-3] 이 -1이 아니라는 가정하에 값이 추가되어야 합니다.

 

최소한의 봉지 개수로 설탕을 배달해야 하므로 arr[i-5]+arr[i-(i-5)] 의 크기를 먼저 조건문으로 넣으면 원하는 값을 구할 수 있게 됩니다.

var line = Int(readLine()!)!

var arr = [-1, -1, -1, 1, -1, 1]

for i in 6...5000 {
    if arr[i-5] != -1 {
        arr.append(arr[i-5]+arr[i-(i-5)])
    } else if arr[i-3] != -1 {
        arr.append(arr[i-3]+arr[i-(i-3)])
    } else {
        arr.append(-1)
    }
    
}

print(arr[line])