[백준] 9461번: 파도반 수열 풀이 및 해설(C++)

문제 이미지

 

풀이

 

 

이미지 확대

새로 생겨나는 큰 삼각형들의 한 변의 길이는

이전 삼각형들의 두변의 길이의 합니다.

 

쭉 나열해보면

 

6번째는(흰색 3) = 5번째(파란색 2)+1번째(파란색 1)

7번째는(파란색 4)=6번째(흰색 3)+2번째(흰색 1)

8번째는(흰색 5)= 7번째(파란색 4)+3번째(파란색 1)

9번째는(파란색 7)=8번째(흰색 5)+4번째(흰색 2)

10번째는(흰색 9)=9번째(파란색 7)+5번째(파란색 2)

11번째는(파란색 12)=10번째(흰색 9)+6번째(흰색 3)

 

어떤 삼각형의 한편 길이는 바로 직전의 삼각형과 5번째 전의 삼각형 한변 길이의 합임을 알 수 있다.

 

따라서 n번째 삼각형의 한 변의 길이를 arr [n]이라고 할 때

arr [n]= arr [n-1]+arr [n-5]라고 할 수 있다.

 

n-5부터 시작하므로 5번째 인덱스까지는 초기값을 1,1,1,2,2로 지정해 준후 공식을 적용하면 된다.

 

 

 

해답 코드

#include <iostream>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;


int main(){
    int n,times;
    cin>>times;
    for(int j=0; j<times; j++){
        cin>>n;
        unsigned long arr[101];
        arr[1]=1;
        arr[2]=1;
        arr[3]=1;
        arr[4]=2;
        arr[5]=2;
        if(n>5){
            for(int i=6; i<n+1; i++){
                arr[i]=arr[i-1]+arr[i-5];
            }
        }
        cout<<arr[n]<<'\n';
    }
    
    return 0;
}

 

해맸던 부분

문제 자체는 직관적으로 바로 보여 쉬운편이다. 하지만 예전에 틀렸던 기록을 보니 초기값을 하나 덜 설정했거나, 배열의 크기를 동적으로 할당해서 틀렸었다. 초기값은 항상 indexerror가 나지 않게 꼼꼼히 설정하고, 가능한 데이터의 길이는 정적으로 할당해야 겠다.