[14495/Swift] 피보나치 비스무리한 수열

*** 언어는 Swift! ***

 

오랜만에 다시 돌아온 블로그 포스팅.. 벌써 9회차가 된 알고리즘 스터디는 이번에 DP 라는 새로운 개념을 이용한 문제들을 풀어보기로 했다.

사실 DP에 대해서는 난생 처음 들어본거라 공부가 필요했다. 스터디장님이 DP에 대해 설명해주시긴 했지만 그래도 내 스스로 이해가 되지 않아서 좀 걱정이었다. 그래서 나중에 DP 관련으로 정리해서 한 번 블로그 포스팅을 하면 좋을 것 같다고 생각된다.

 

자 그럼 이번에도 문제를 풀어보자 이번에는 14495번의 피보나치 비스무리한 수열 이라는 제목을 가진 문제였다.

자세한 문제는 아래와 같다.

 

기존의 피보나치 수열은 1 1 2 3 5 처럼 앞의 수들을 더한 값이 다음 값이 되는 수열이었는데 이번 문제는 제목처럼 피보나치 비스무리한 수열이었다.

문제가 어렵지 않았는데 그 이유는 식이 이미 제공되었기 때문이다.

자 그럼 이번에도 쪼개보자.

 

1. 자연수 n을 입력받는다.

2. f(1) = f(2) = f(3) = 1 이다.

3. 피보나치 비스무리한 수열은 f(n) = f(n - 1) + (f - 3)인 수열이다.

 

자 그럼 위에 적은대로 문제를 풀어보자

 

1. 자연수 n을 입력받는다.

이제는 너무나도 많이 해본 자연수 n을 입력받아 보자.

let n = Int(readLine()!)!
var result: Int = 0
var resultArray: [Int] = [Int](repeating: 1, count: 117)

값을 구하기 위한 result와 수열을 저장하기 위한 resultArray를 만들어준다.

여기서 resultArray는 미리 1로 초기화해준 뒤 문제의 범위 만큼 만들어 준다. n(1 <= n <= 116) 

초기값을 1로 해준 이유는 1, 2, 3 번째 값이 모두 1이기 때문이다. 여기서 2번째 순서에 대한 내용도 만족하게 된다.

 

3. 피보나치 비스무리한 수열은 f(n) = f(n - 1) + (f - 3)인 수열이다.

자 그럼 이제 실제로 수열을 구해보자. 먼저 1, 2, 3 번째 값은 모두 1이기 때문에 3번째 이후의 값부터 구해야한다.

위의 식을 실행하기 위해서는 3번째 이후의 값만 해당되기 때문에 조건문을 통해 n이 3이상일 때만 실행하도록 한다.

if n > 3 {

그 다음으로 3이상이기 때문에 for문을 이용해 4번째 수열부터 구한다.

식은 위에 나온대로 f(n - 1) + f(n - 3) 을 이용해 배열에 값을 넣어준다.

for i in 4...n {
    result = resultArray[i - 1] + resultArray[i - 3]
    resultArray[i] = result
}

이제 n번째 배열만 출력해주면 우리가 원하는 값을 얻을 수 있다. if문 내부의 전체 코드는 아래와 같다.

if n > 3 {
    for i in 4...n {
        result = resultArray[i - 1] + resultArray[i - 3]
        resultArray[i] = result
    }
}

print(resultArray[n])

 

간단한 DP문제였지만 DP의 개념에 대해 확실하지 않은 나는 이해하는데 조금 시간이 걸렸던 것 같다.

그래도 오늘도 한 건 해결! *.☆⸜(⑉˙ᗜ˙⑉)⸝♡.*