[BOJ] 9461번 : 파도반 수열 (C++)

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

9461번: 파도반 수열

 

dp문제이다. 

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다.

P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

수열을 보게 되면 피보나치와 같은 규칙이 있음을 알 수 있다. 

내가 i번째 수라고 했을 때, i번째 수는 i-3번째 수와 i-2번째 수를 더한 값이 되는 것이다. 

따라서 d[i] = d[i-3]+d[i-2]; 가 된다. 

테스트케이스가 T번 나오므로 그 때마다 dp를 돌려 값을 구하는 것보다, 아예 d배열을 모두 채우고 필요한 값을 가져다쓰는 것이 더욱 효율적이다. 

그래서 1 ≤ N ≤ 100이므로 값이 int범위를 벗어날 수 있다. 

int형 대신 long long형을 써주어야 통과할 수 있다. 

 

추가로 또다른 규칙을 찾을 수 있다. 

현재 i번째 수는 i-5번째 수와 i-1번째 수를 더하여 구할 수도 있다.

 

#include <iostream>
using namespace std;
typedef long long ll;

//d[i]=k : k값은 p(i)이 됨
//d[i] = d[i-3]+d[i-2];
ll d[102]; 

int main(){
    //초기값 설정
    d[1]=1; d[2]=1; d[3]=1;
    
    for(int i=4; i<=100; i++){
        d[i] = d[i-3]+d[i-2];
    }

    int tc; cin>>tc;
    while(tc--){
        int x; cin>>x;
        cout<<d[x]<<'\n';
    }
}