66. C++ 백준 1003 번 피보나치 함수 자세한 설명
안녕하세요 코딩하는 덕구입니다.
C++ 백준 1003 번 피보나치 함수입니다.
다이나믹 알고리즘 문제입니다.
https://www.acmicpc.net/problem/1003
1003번: 피보나치 함수
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
www.acmicpc.net
input N이 주어졌을 때 0, 1이 출력되는 횟수를 구해서 출력하는 문제입니다.
기본적인 전제입니다.
fibonacci(0)은 0을 출력하게 됩니다. (문제에 주어진 코드의 구현상)
fibonacci(1)은 1을 출력하게 됩니다. (문제에 주어진 코드의 구현상)
N이 2일 때 ( fibonacci(2)는 )
fibonacci(1), fibonacci(2)를 호출하게 되고
fibonacci(1)의 출력 1, fibonacci(0)의 출력 0
즉 fibonacci(2)는 1을 1번 출력하고, 0을 1번 출력하게 됩니다.
그럼 fibonacci(3)은 어떻게 될까요?
fibonacci(3) = fibonacci(2) + fibonaci(1)
fibonacci(2)는 방금 구했죠, 1을 1번 0을 1번
fibonacci(1)은 문제에 주어졌습니다. 1을 1번 0을 0번
fibonacci(3) 은 1을 2번, 0을 1번
즉 fibonacci(3)의 1과 0이 등장한 횟수는
fibonacci(2)에서 등장한 1과 0의 횟수 + fibonacci(1)에서 등장한 1과 0의 횟수라는 것을
알 수 있습니다.
위와 같은 방법으로 접근하여 코드를 구현해 봅시다.
각 index별 0이 등장한 횟수, 1이 등장한 횟수를 담는 배열을 선언합니다.
input N은 최대 40까지이고, 0일때의 값, 1일때의 값만 저장하면 되므로 아래와 같이 공간을 할당합니다.
int arr[41][2] = {0,};
0과 1의 fibonacci 함수에서의
0이 출력되는 횟수, 1이 출력되는 횟수입니다.
문제에서 주어진 초기 값 입니다.
arr[0][0] = 1; arr[0][1] = 0; //N이 0일때 0은 1번, 1은 0번 출력
arr[1][0] = 0; arr[1][1] = 1; //N이 1일때 0은 0번, 1은 1번 출력
input N의 0과 1이 등장한 횟수가 배열에 있는지 체크를 하고
만약 있다면 0이 등장한 횟수, 1이 등장한 횟수를 출력합니다.
if ( N <= len ) cout << arr[N][0] << " " << arr[N][1] << endl;
만약 없다면 없는 숫자부터 N까지
0이 등장한 횟수, 1이 등장한 횟수를 구해서 차례대로 채우고 난 후
input N의 0이 등장한 횟수, 1이 등장한 횟수를 출력합니다.
else{
for (int n = len + 1; n <= N; n++){
arr[n][0] = arr[n-1][0] + arr[n-2][0];
arr[n][1] = arr[n-1][1] + arr[n-2][1];
}
cout << arr[N][0] << " " << arr[N][1] << endl;
}
C++ 백준 1003 번 최종 코드입니다.
#include <iostream>
using namespace std;
int arr[41][2] = {0,};
int main(){
int T, N, len = 1;
cin >> T;
arr[0][0] = 1; arr[0][1] = 0; //N이 0일때 0은 1번, 1은 0번 출력
arr[1][0] = 0; arr[1][1] = 1; //N이 1일때 0은 0번, 1은 1번 출력
for(int t = 0; t<T; t++){
cin >> N;
if ( N <= len ) cout << arr[N][0] << " " << arr[N][1] << endl;
else{
for (int n = len + 1; n <= N; n++){
arr[n][0] = arr[n-1][0] + arr[n-2][0];
arr[n][1] = arr[n-1][1] + arr[n-2][1];
}
cout << arr[N][0] << " " << arr[N][1] << endl;
}
}
return 0;
}
C++ 백준 1003 번 피보나치 함수이었습니다. 감사합니다.