[C/C++ 백준 9461번] 파도반 수열 (Silver 3)

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

9461번: 파도반 수열

실버 3이라 그런지 정말 쉽다. 삼각형을 보다 보면 N번째 삼각형의 변의 길이는 N-1번째와 N-5번째 삼각형의 길이를 합한 것임을 눈치챌 수 있다.

 

다만, 100번째 삼각형의 변의 길이는 int형의 범위를 넘음에 주의하자. 배열의 자료형을 long long int로 선언하면 해결 된다.

 

#include <stdio.h>
long long N[101]={1,1,1,2,2,3,4,5,7,9,};
 
int main(void){
    for(int i=10; i<101; i++){
        N[i]=N[i-1]+N[i-5];
    }    
    int T;
    scanf("%d",&T); 
    int test;
    for(int j=0; j<T; j++){
        scanf(" %d",&test);
        printf("%lld\n",N[test-1]);
    }
}