[C++] 백준 9461번 - 파도반 수열

---

0. 문제

 

https://www.acmicpc.net/problem/9461

 

1. 아이디어

 

1) 순서대로 그림을 따라서 그려보니까, P(5) 이후의 삼각형들은 모두 시계방향으로 도는 규칙을 가지고 있다. 따라서 점화식을 세웠을 때 P(N) = P(N -1) + P(N - 5) 라는 사실을 발견!

 

2. 소스코드

 

#include <iostream>
int main()
{
    int T;
    long long dp[101];
    std::cin >> T;
    dp[1] = 1; dp[2] = 1; dp[3] = 1; dp[4] = 2; dp[5] = 2;
 
    for (int r = 0; r < T; r++)
    {
        int N;
        std::cin >> N;
        for (int i = 6; i <= N; i++)
            dp[i] = dp[i - 1] + dp[i - 5];
        std::cout << dp[N]<<'\n';
    }
}

 

3. 결과

 

 

4. 피드백

 

• 항상 오버플로우 조심 ㅜㅜ

---