[13699/Swift] 점화식

*** 언어는 Swift! ***

 

이번에도 저번과 마찬가지로 DP를 이용한 문제이다. 이번 문제도 쉽지 않았지만 문제 속에 힌트가 있었기 때문에 그나마 풀어볼 수 있었던 문제였던 것 같다.

거두절미하고 자세한 문제는 아래와 같다.

문제 속에 식이 있기 때문에 저 식을 이용해 풀면 된다.

단순히 식만 봤을 때는 t(0) * t(n-1) 이 1씩 늘어나면서 계속 반복되는 걸 알 수가 있다.

 

내가 집중한 건 저 식이 언제까지 반복되느냐이다. 만약 n이 5라면 아래와 같은 식이 나올 것이다.

t(5) = t(0) * t(5-1) + t(1) * t(5-2) + t(2) * t(5-3) + t(3) * t(5-4) + t(4) * t(5-5) 

이걸 더하기 기준으로 쪼개보면 t(0), t(1), t(2) ... 로 하나씩 더해서 올라가고

t(n-1), t(n-2), t(n-3)... 로 하나씩 빼다가 결국엔 t(n-n) 이 될 때까지 계속 반복하게 된다.

그럼 이렇게 생각하고 문제를 쪼개보자.

 

1. 첫째 줄에 n이 주어진다.

2. 35개까지 받을 수 있다.

3. t(0) * t(n - 1) + t(1) * t(n - 2) 로 계속 더한다.

 

크게 어렵지 않게 쪼갤 수 있다.

 

1. 첫째 줄에 n이 주어진다.

let n = Int(readLine()!)!

n을 받는 건 많이 해보았으니 설명은 생략한다.

 

2. 35개까지 받을 수 있다.

var numberArray: [Int] = [Int](repeating: 0, count: 36)

numberArray[0] = 1
numberArray[1] = 1
numberArray[2] = 2
numberArray[3] = 5

여기서 주목할 건 문제 속에서 n의 범위가  n (0 ≤ n ≤ 35) 이라고 알려줬기 때문에 DP를 이용해 푸는 만큼 미리 그 만큼의 배열을 만들어놓기로 했다.

그리고 문제 속에서 t(0) ~ t(3) 까지의 답은 나와있기 때문에 따로 구하지 않고 바로 바로 배열에 넣어놔준다.

이렇게까지하면 준비가 모두 끝나게 된다.

 

3. t(0) * t(n - 1) + t(1) * t(n - 2) 로 계속 더한다.

var plus = 0
var minus = 1
var sum = 0

if n > 3 {
    for i in 4...n {
        while i - minus >= 0 {
            sum += numberArray[plus] * numberArray[i - minus]

            plus += 1
            minus += 1
        }

        numberArray[i] = sum
        plus = 0
        minus = 1
        sum = 0

    }
}

우리는 t(3) 까지는 이미 알고 있고, 배열에 넣어주었으니 n이 그 이상의 값이 들어왔을 경우에만 계산을 해보자.

나는 이 계산을 하기 위해 세 개의 변수를 만들어 줬다.

plus 는 t(0), t(1), t(2).. 가 하나씩 늘어나는 index를 표시해줄 변수

minus는 t(n-1), t(n-2), t(n-3)... 가 하나씩 늘어나는 index를 표시해줄 변수

sum은 합산을 위한 변수

 

for문으로 들어와 3이후부터 돌면서 n-minus 값이 0이 될 때까지 while 문을 돌린다.

그렇게 되면 n이 5가 들어오면 minus가 5가 될 때까지 계속해서 돌게 된다.

 

한 번 while문을 다 돌면 해당 위치에 합산된 결과를 넣어주는 것과 초기화 해주는 것을 잊지 말고 해줘야 다음 숫자의 값을 구할 수 있다.

 

문제에서는 n번째 값을 알아내는 것이 목적이니, 마지막에 배열의 n번째 값을 출력해준다.

print(numberArray[n])

 

이렇게 하면 점화식대로 계산된 n번째 값을 얻어낼 수 있다!

오늘 한 건 해결 ◝(・▿・)◜