백준(BOJ) 동적프로그래밍 파도반 수열 (9461) - Silver 3

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

문제

9461번: 파도반 수열

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

출력

각 테스트 케이스마다 P(N)을 출력한다.

문제 해결

동적계획법의 전형적이 문제이다. 파도반 수열에 대해 잘 몰라도 패턴을 보면 피보나치와 비슷하여 쉽게 해결이 가능하다. 피보나치 문제를 푸는것과 비슷하게 가장 작은값들에 대한 basecase를 설정해주고 바텀업 방식으로 작은값부터 테이블을 채우면서 재귀적으로 풀면 쉽게 해결이 가능하며 재귀식은 P(N) = P(N-2) + P(N-3)으로 피보나치와 상당히 유사하다. 난이도는 그렇게 높지 않으며 아주 간단하게 해결이 가능한 문제이다.

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define SIZE 101

using namespace std;
typedef long long ll;

vector<ll>dp(SIZE, 0);

ll Padovan(ll N){
    if(N<=3)
        return 1;
    if(dp[N] == 0)
        dp[N] = Padovan(N-2) + Padovan(N-3);
    return dp[N];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt", "r" ,stdin);
    
    ll N = 0;
    ll testCase= 0;
    
    cin >> testCase;
    while(testCase--){
        cin >> N;
        cout << Padovan(N) << "\n";
    }
    return 0;
}