백준 9461 파도반 수열 / C++

문제 : 9461

풀이 point

규칙을 찾는 것이 포인트이다. 자세히 보면 삼각형의 변 합이 새로운 삼각형의 변의 길이가 되는 것을 알 수 있다.

풀이 방법

이를 점화식으로 나타내보 dp[i] = dp[i-2] + dp[i-3]이라는 것을 알 수 있다.

참고로 값이 int 범위를 넘을 수 있으므로 long long으로 배열을 선언해주는 것이 좋다.

코드

//백준 9461, 파도반 수열

#include <iostream>

long long dp[101];

int main (){

    int T, N;
    std::cin >> T;
    
    dp[1] = 1; dp[2] = 1; dp[3] = 1;
    for(int i{4}; i<=101; ++i){
        dp[i] = dp[i-2] + dp[i-3];
    }
    
    while(T--){
        std::cin >> N;
        std::cout << dp[N] << '\n';
    }

    return 0;
}