백준 - 9461

문제링크

 

문제요약

나선형 모양으로 삼각형이 계속해서 추가될때, n번째 삼각형의 변의 길이를 구하는 문제이다.

풀이

나선형모양의 삼각형이 계속 추가된다해서 어렵게 생각할 필요없다.

문제에서 P(10)의 예시를 주어지는데 이 수열이 어떻게 증가하는지 찾고 DP로 해결 하면되는 문제이다.

삼각형의 변의 길이는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9씩 증가한다.

증가하는걸 자세히보면 n번째는 (n - 2) + (n - 3) 만큼 증가한다는걸 알 수 있다.

처음 P(4)까지의 값을 세팅하고 이를 통해 P(100)까지 값을 구한뒤 P(n)을 출력해주면된다.

---

소스코드

#include <iostream>
#include <vector>
using namespace std;

long long dp[105];
int n;

int main() {
    cin >> n;

    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 2;
    dp[4] = 2;
    for (int i = 5; i < 100; i++) {
        dp[i] = dp[i - 2] + dp[i - 3];
    }
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        cout << dp[tmp - 1] << '\n';
    }
}