[백준/c++] BOJ 9461 - 파도반 수열

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

9461번: 파도반 수열

 

문제 설명

삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 나선에서 가장 긴 변의 길이를 k라고 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. P(N)은 나선에 있는 정삼각형의 변의 길이이다. N이 주어졌을 때, P(N)을 구한다.

(1 <= N <= 100)

해결

나는 그림을 보면서 규칙성을 찾았다. 처음 삼각형 5개는 그대로 두고, 변의 3인 삼각형부터 봐 보자.

변이 3인 삼각형은 6번째 삼각형인데, 1번째, 5번째 삼각형과 맞닿아 있다.

변이 4인 삼각형은 7번째 삼각형이고, 2번째, 6번쨰 삼각형과 맞닿아 있다.

변이 5인 삼각형은 8번째 삼각형이고, 3번째, 7번째 삼각형과 맞닿아 있다.

 

여기에서 점화식을 세울 수 있다.

P(N) = P(N - 5) + P(N - 1)

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
#define INF 1e9
using namespace std;

int t, n;
long long dp[105] = { 0,1,1,1,2,2 };

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

    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n;
        for (int j = 6; j <= n; j++)
            dp[j] = dp[j - 5] + dp[j - 1];

        cout << dp[n] << "\n";
    }
}