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

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

# 문제 설명

다음과 같이 n번째 피보나치 수를 구하는 c++ 함수가 있다.

이 함수는 n번째 피보나치 수를 반환하고, 0과 1을 출력한다.

문제는 0과 1이 각각 몇 번 출력되는지 구하는 것이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

 

# 입출력 예시

입력	출력
3 0 1 3	1 0 0 1 1 2
2 6 22	5 8 10946 17711

 

# 문제 풀이

def fibos_no(n):
    zero = {0:1, 1:0}
    one = {0:0, 1:1}
    for i in range(2, n+1):
    	zero[i] = zero[i-1]+zero[i-2]
        one[i] = one[i-1]+one[i-2]
    
    return zero[n], one[n] # 0, 1 개수

T = int(input())
for _ in range(T):
	print(*fibos_no(int(input())))

 

# 핵심 포인트

- 피보나치 수는 i번째 항이 i-1번째 항과 i-2번째 항의 합으로 계산한다. 다시 말해 귀납적으로 풀어야해서, 함수의 재귀 호출로 풀거나 작은 문제로 큰 문제를 해결하는 DP 알고리즘으로 풀 수 있다. 여기서 DP로 푸는 것이 더 효율적이다.

- 문제는 거쳐온 피보나치 수의 2진수을 보고, 0과 1의 개수를 구하는 것이다. 문자열을 담아 0의 갯수와 1의 갯수를 확인할 수도 있지만, 0의 개수와 1의 개수를 정수로 저장하는 것이 더 효율적이다.