[BOJ / C++] 26529번 : Bunnies

문제 (Google 번역)

당신은 농장 동물을 키울 것이고 가장 쉬운 동물인 토끼부터 시작하기로 결정했습니다. 놀랍게도 그들은 토끼처럼 번식하고 있어서 정확하게 셀 수 없습니다. 그러나 토끼의 번식 패턴은 항상 피보나치 수열을 따릅니다. 피보나치 수열은 다음과 같이 정의됩니다.

F(0) = 1, F(1) = 1, F(N) = F(N-1)+F(N-2)

토끼가 번식한 개월 수를 감안할 때 피보나치 수열을 사용하여 가져야 할 토끼의 수를 결정하십시오.

입력

첫 번째 줄에는 다음 데이터 세트의 수를 나타내는 단일 정수 n이 포함됩니다. 각 데이터 세트는 초기 토끼 한 쌍을 구입한 이후 경과한 개월 수를 나타내는 단일 정수 x로 시작합니다. 0≤x≤45

출력

각 테스트 케이스에 대해 x개월 후 예상되는 토끼 수를 출력합니다.

Solved.ac 레벨

브론즈 II

풀이

DP라고 하기에도 민망한 피보나치 수 관련 문제였다. 

점화식도 문제에 제시되어 있어 어려울게 하나도 없었지만 문제의 의도를 파악하는게 조금 힘들었다.

출력이 각 테스트 케이스에 대해서 이뤄져야 하는줄 알고 while문에서 각각의 테스트 케이스에 대한 값을 출력해줬는데, 입력된 값을 모두 받아놓았다가 한 번에 결과를 출력해줘야 하는 문제였다.

Code

#include<bits/stdc++.h>

using namespace std;

int t;
vector<int> input;
int dp[45];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> t;

    dp[0] = 1;
    dp[1] = 1;

    while(t--) {
        int n;
        cin >> n;
        input.push_back(n);
    }

    for(int i = 2; i <= *max_element(input.begin(), input.end()); i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    for(auto it = input.begin(); it != input.end(); it++) {
        cout << dp[*it] << "\n";
    }

    return 0;
}

 

26529번: Bunnies