9461번

9461번 - 파도수열

D[N] = N번째 삼각형의 변의 길이

이 문제를 풀기 위해서는 규칙을 찾아야했다. 

처음에는 도형적인 측면에서 그룹핑을 하다가 잘 안되는 것을 발견하고

몇번째 삼각형이 몇번째에 영향을 미치는가 보기 위해서 하나씩 적어가면서 규칙을 찾기 시작했다.

N이 1~4일 때는 규칙이 발생하지 않지만 N=5일 때부터 규칙이 발생하는 것이 보였다. 그림으로 찾는게 더 쉽다.

N=5일때는 N=4일때와 N=0일 때의 변의 합이 되고

N=6일때는 N=5일때와 N=1일 때의 변의 합이 답이 된다.

이를 통해서 

D[N] = D[N-1] + D[N-5] 라는 식을 도출해낼 수 있었다. (단, N이 5 이상일 때)

그래서 N 이 0~4 까지의 값은 따로 표현을 해 주었다.

하지만! 평상시처럼 int형을 쓰고 N의 최대값을 넣어서 답을 확인해 보지 않으면 틀릴 수 있다.

문제에서 주어진 N=100 일때는 int 형 변수의 범위를 초과하기 때문에 long long 으로 바꿔줘야 했다!! ( 항상 끝값 확인하는 버릇 !)

<정답 코드>

#include<iostream>
using namespace std;
long long D[101];
long long go(int n)
{
    if(n<=0)
    {
        return 0;
    }
    if(n==1 || n==2 || n==3)
    {
        return 1;
    }
    if(n==4)
    {
        return 2;
    }
    
    if(D[n] != 0)
    {
        return D[n];
    }
    
    D[n]=go(n-1)+go(n-5);
    
    return D[n];
    
}
int main()
{
    int tc;
    cin>>tc;
    
    for(int t=1;t<=tc;t++)
    {
        for(int i=0;i<101;i++)
        {
            D[i]=0;
        }
 
        int N;
        cin>>N;
        cout<<go(N)<<endl;
    }
    return 0;
}