[Dynamic Programming] 네트워크 선 자르기

DP란?

(수학의 점화식 개념)
큰 문제를 작은 단위의 문제로 나눈다
-> 작은 문제의 해답을 저장(memorization) 후 이 값을 이용해 더 조금 더 큰 답을 구한다
-> 결국 최종 해답을 구한다

문제

해답

import Foundation

func numberOfWaysToCutNetworkLine(_ n: Int) -> Int {
    var dy = [Int](repeating: 0, count: n + 1)
    dy[1] = 1
    dy[2] = 2
    for i in 3...n {
        dy[i] = dy[i - 1] + dy[i - 2]
    }
    return dy[n]
}

// Example Usage
let n = 17
print(numberOfWaysToCutNetworkLine(n))

1. 먼저 1m 길이 네트워크 선 자르는 방법을 구하고 dy배열에 담는다
2. 다음으로 2m 길이 네트워크 선 자르는 방법을 구하고 dy배열에 담는다
3. 이제 3m부터는 점화식으로 해결한다. 예를들어 3m의 경우 1m선 자르는 방법 + 2m선 자르는 방법으로 해결한다