(파이썬) 백준 1003번 : 피보나치 함수 - 컴도리돌이

 

 

---

문제

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를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

---

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

예제 입력

3

0

1

3

예제 출력

1 0

0 1

1 2

---

코드

기본적인 피보나치 함수 문제랑 다른 문제인데, 피보나치 함수는 0번째는 0 , 1번째는 1 , (n>=2) 번째부터는 n-1번째 수와 n-2 번째 항의 합으로 나열되는 함수입니다. 

요번 백준 1003번 문제는 0의 개수와 1의 개수를 구하는 건데 

예를 들면  2번째 항은  0번째 항과 1번째 항의 합입니다. 3번째 항은 1번째 항과 2번째 항의 합인데, 2번째 항은 0번째 항과 1번째 항이기 때문에 0번째 항이 1개 있고 1번째 항이 2개 있어서 출력 값이 (1 2)로 나옵니다.

 

 

 

백준 1003번 -컴도리돌이

 

처음 문제를 접했을 때 이 0번째 항의 개수와 1번째의 항의 개수도 피보나치 함수처럼 나열돼서 단순하게 피보나치로 풀었지만 시간 초과가 떠서 멘붕에 빠졌습니다... :-((

 

그래서 요번에는 인터넷을 참조하여 많은 분들이 배열을 사용하는 것보고 배열을 사용하면 함수 호출 방식보다 더 시간이 단축될 수 있다는 것을 깨닫게 되었습니다. 하하하

 

 

백준 1003번 -컴도리돌이

 

일단 코드를 짜기 전제 노트에다가 0과 1의 개수가 어떻게 나열되는지 확인해야 합니다.

0은 처음에 1,0,1로 나열되고 1은 0,1,1로 나열되어서 뒤에 n번째부터는 피보나치 함수처럼 나열됩니다.

그래서 c0과 c1를 배열로 만들어 , 어차피 c0과 c1은 n번째 항의 0의 개수와 1의 개수의 배열이기 때문에 출력 값을 c0 [n] , c1 [n] 이렇게 출력해도 됩니다.

생각보다 어려운 문제였습니다. ㅠㅠㅠ백준은 시간 초과 때문에 더욱 어려운 거 같아요 이 코드가 정답은 아니지만 공유합니다~~

 

다음 포스팅에서 만나요!