[백준] 1003번 : 피보나치 함수 - (c++, c, python/파이썬, java/자바)

• 문제

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

---

• 알고리즘 ( 접근 )

처음엔 문제에 나와있는대로 함수로 구하였지만, 시간초과가 났다.

이 문제는 dynamic programing ( 동적 계획법 ) 으로 풀 수 있다.

 

N	0의 출력 개수	1의 출력 개수
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3

이 표를 토대로 보면 0의 출력 개수는 DP[N-1]개, 1의 출력 개수는 DP[N]개라는 것을 알 수 있다.

---

• 풀이 - C++( C )

#include <iostream>

using namespace std;

int dp[41] = { 0 , 1, 1 };

int main()
{
    int T, i, n;
    for (i = 3; i < 41; i++) dp[i] = dp[i - 1] + dp[i - 2];

    cin >> T;

    while (T--)
    {
        cin >> n;
        if (n == 0) cout << "1 0\n";
        else cout << dp[n - 1] << " " << dp[n] << "\n";

    }
}

#include <stdio.h>

int dp[41] = { 0 , 1, 1 };

int main()
{
    int T,i,n;
    for (i = 3; i < 41; i++) dp[i] = dp[i - 1] + dp[i - 2];

    scanf("%d", &T);
    
    while (T--)
    {
       
        scanf("%d", &n);
        if (n == 0) printf("%d %d\n", 1, 0);
        else printf("%d %d\n", dp[n - 1], dp[n]);

    }
}

• 풀이 - JAVA

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		int[] dp = new int[41];
		
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 1;
		
		for(int i = 3; i < 41; i++)
			dp[i] = dp[i-1] + dp[i-2];
		
		while(T-->0)
		{
			int n = sc.nextInt();
			if(n == 0) System.out.println("1 0");
			else System.out.printf("%d %d%n", dp[n-1], dp[n]);
		}
	}
}

• 풀이 - PYTHON

t = int(input())
dp = [0,1,1]

for i in range(3,41):
   dp.append(dp[i-1] + dp[i-2])


for i in range(t):
    n = int(input())
    if n == 0:
        print("1 0")
    else: print(dp[n-1], dp[n])