작심큰일 챌린지 - Day 5. 피보나치 비스무리한 수열 (미들러, Python)

출처 - 작심큰일 챌린지 메인 페이지

 

 

벌써 한 주가 지났다.

 

5일차는 이번 주 마지막 문제이고, 주말에는 보너스 문제가 나온다.

 

---

Day 5. 피보나치 비스무리한 수열

 

오늘의 문제는 백준 프로그래밍 14495번 문제다.

 

문제

피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다.

 

1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ...

 

자연수 n을 입력받아 n번째 피보나치 비스무리한 수열을 구해보자!

 

입력

• 자연수 n(1 ≤ n ≤ 116)이 주어진다.

 

출력

n번째 피보나치 비스무리한 수를 출력한다.

 

예제 입력 1

10

예제 출력 1

19

 

 

---

풀이 과정

 

기존 피보나치 수열과의 차이점

 

문제 자체는 피보나치 수열과 상당히 유사했고, 큰 차이가 없어 보였다.

 

한 가지 다른 점은 두 번째가 아닌 세 번째 이전 값을 더한다는 점이다.

 

먼저 기본 피보나치 수열의 점화식을 적어 보았다.

 

$f(n) = f(n-1) + f(n-2)$

 

여기에서 기존의 다른 점을 적용하면 식이 다음과 같이 변한다.

 

$f(n) = f(n-1) + f(n-3)$

 

좀 더 직관적으로 예시들을 살펴보면 다음과 같다.

1, 1, 2, 3, 5, 8, 13, 21, ... (기존 피보나치 수열)
1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ...(피보나치 비스무리한 수열)

 

기본 피보나치는 바로 이전 두 항을 더하지만, 피보나치 비스무리한 수열은 앞의 한 항과 세번째 이전 항을 더하다는 점이 유일한 차이점으로 보인다.

 

즉, 전체 구현 방식에는 차이가 없고, 점화식을 기준으로 참조하는 인덱스 값만 바꿔주면 된다는 것을 알 수 있다.

 

구현

일단 점화식을 기반으로 한 기존 피보나치 수열을 구현하는 코드를 구현했다.

 

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 1
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

 

여기에서 피보나치 비스무리한 수열의 방식대로 참조하는 인덱스를 세 번째 이전 항으로 변경했다.

def pseudo_fibonacci(n):
    dp = [1] * 117  # 문제에서 n ≤ 116
    for i in range(4, n+1):
        dp[i] = dp[i-1] + dp[i-3]
    return dp[n]

 

---

 

개선점

DP 성애자(?)라 그런가, 문제 자체는 쉬웠다. 

 

하지만 여전히 아쉬운 점은 디테일인 것 같다. 아래는 내가 제출한 코드와 해설 코드에서의 차이다.

 

// 제출 코드
import sys

input = sys.stdin.readline
N = int(input())

def pseudo_fibonacci(n):
    dp = [1] * 117
    for i in range(4, n+1):
        dp[i] = dp[i-1] + dp[i-3]
    return dp[n]

print(pseudo_fibonacci(N))

 

// 풀이 코드
n = int(input())
dp = [1]*117
for i in range(4, n+1):
    dp[i] = dp[i-3] + dp[i-1]
print(dp[n])

 

 

난 dp 테이블을 내부적으로만 사용하고 바로 반환하는 방식을 채택했는데, 이 경우 최종 print 시 결국 사용하는 방식은 같다. 

 

따라서 해설 코드처럼 dp 테이블을 외부에 선언하고, 할당하여 사용하는 것이 더 좋다고 생각한다.

 

함수도 별도로 선언할 필요가 없기 때문에 더 깔끔한 접근이라고 생각했다.

 

또한, 문제에서 입력 크기를 제한했기 때문에 별도 import도 쓰지 않는 것이 더 좋지 않나? 라는 생각도 들게 된 것 같다. 어차피 입력을 많이 받는 것도 아닌데 굳이 코드를 길게 늘릴 이유는 없는 것 같다는 생각이 들었다. 이전에 입력 시간 떄문에 시간 초과가 발생한 적이 있어서, 잘못된 습관이 들었던 것 같다.

 

불필요한 코드를 굳이 넣을 필요는 없으니, 앞으로 이런 부분도 좀 더 신경을 써야겠다.