알고리즘 설계 실습 - Fibo_counter

---

문제

피보나치 수는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 아래 소스 코드는 N번째 피보나치 수를 구하는 재귀함수이다.

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

fibonacci(3)을 호출하면 다음과 같이 동작한다.

- fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출

- fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출

- 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴

- fibonacci(0)은 0을 출력하고, 0을 리턴

- fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴

- 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴

- fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다. 이 때, 0은 1번 출력되고, 1은 2번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출한 경우, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하라.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어집니다. 둘째 줄부터 T개의 N이 주어진다. N은 40보 다 작거나 같은 자연수 또는 0이다.

출력

T개의 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력 하세요.

 

입력 예시

1

3

0

1

3

 

출력 예시

1

1

0

0

1

1

2

---

정답 코드

def fibonacci_count(n):
    # 각 n에 대해 '0'과 '1'이 출력되는 횟수를 저장할 배열 초기화
    zero_count = [0] * (n+1)
    one_count = [0] * (n+1)
    
    # 기본 조건 설정
    if n >= 0:
        zero_count[0] = 1
    if n >= 1:
        one_count[1] = 1
    
    # 2부터 n까지 각각의 수에 대해 '0'과 '1'의 출력 횟수 계산
    for i in range(2, n+1):
        zero_count[i] = zero_count[i-1] + zero_count[i-2]
        one_count[i] = one_count[i-1] + one_count[i-2]
        
    return zero_count, one_count

# 최대 N 값 40으로 모든 경우를 미리 계산
max_n = 40
zero_count, one_count = fibonacci_count(max_n)

# 입력받을 테스트 케이스의 수 T
T = int(input().strip())

# T개의 테스트 케이스 처리
for _ in range(T):
    N = int(input().strip())
    print(zero_count[N], one_count[N])

위 코드에서 우선, `fibonacci_count` 함수는 0부터 주어진 최대 값(max_n)까지 각 숫자에 대해 '0'과 '1'이 출력되는 횟수를 계산하여 저장한다. 다음으로, 이 함수는 미리 계산된 결과를 이용하여 사용자가 입력한 각 테스트 케이스(N 값)에 대해 '0'과 '1'이 출력된 횟수를 효율적으로 반환한다. 이를 통해 재귀 호출의 중복 계산을 방지하며, 실행 시간을 단축시킨다.

---