[백준] 1003 - 피보나치 함수

🖥️ 시작하며

시간 제한이 0.25초인 것을 봤을 때, 통상적인 재귀적 접근으로는 이 문제를 해결할 수 없을 것 같다.

그렇다면 동적 계획법이나 수학적으로 접근 가능한지 한번 생각해보자. 우선 딱 봤을 때 수학적으로는 접근하기 힘들어보인다. 그렇다면, 우선 0과 1의 호출 패턴에 대해 분석해보자.

호출 패턴의 점화식은 여전히 fibonacci 함수에 의존한다. 어차피 는 피보나치 함수가 호출되는 만큼 호출되므로 점화식은 같다.

초기 조건을 비교해보자.

피보나치의 초기 조건을 아래와 같다.

또한 의 초기 조건은 아래와 같다.

초기 조건이 반대이므로, 수열의 값이 한 칸씩 밀리게 된다. 이는 하나씩 대입해가면서도 경험적으로 알 수 있다.

		일치 여부
0	(정의되지 않음)	N/A
1		✅
2		✅
3		✅
4		✅

위 과정을 거치면 자연스레 임을 알 수 있다.

⚙️ 코드


def Solution(N):
    if N == 0:
        return 1, 0
    elif N == 1:
        return 0, 1
    else:
        dp = [0 for _ in range(N + 1)]
        dp[0] = 0
        dp[1] = 1

        for i in range(2, N + 1):
            dp[i] = dp[i - 1] + dp[i - 2]

        return dp[N - 1], dp[N]


if __name__ == "__main__":
    import sys

    T = int(sys.stdin.readline())

    for i in range(T):
        N = int(input())
        print(*Solution(N))


#include <stdio.h>

void Solution(int N, int* zero_count, int* one_count) {
    static int dp[41] = {0, 1};  // 첫 두 개의 값만 초기화

    if (N == 0) {
        *zero_count = 1;
        *one_count = 0;
        return;
    } else if (N == 1) {
        *zero_count = 0;
        *one_count = 1;
        return;
    }

    for (int i = 2; i <= N; i++) {
        if (dp[i] == 0) {  // 아직 계산되지 않은 경우
            dp[i] = dp[i - 1] + dp[i - 2];
        }
    }

    *zero_count = dp[N - 1];
    *one_count = dp[N];
}

int main() {
    int T, N;
    int zero_count, one_count;

    scanf("%d", &T);

    for (int i = 0; i < T; i++) {
        scanf("%d", &N);
        Solution(N, &zero_count, &one_count);
        printf("%d %d\n", zero_count, one_count);
    }

    return 0;
}

[백준] 1003 - 피보나치 함수

🖥️ 시작하며

⚙️ 코드

📌 소감

댓글