[삼성 알고리즘] Dynamic Programming(파도반 수열)

안녕하세요 이번 포스팅은 동적프로그래밍으로 백준의 파도반 수열입니다.

 

이번 포스팅은 정삼각형을 추가하며 나선을 만드는 문제입니다. 문제에서 임의의 숫자 N이 주어졌을 때 즉 N 번째 추가한 정삼각형의 변의 길이를 출력하는 문제 입니다.

 

1. 문제 이해

해당 문제는 정삼각형을 추가하여 나선을 만드는 문제로 나선을 만들어 가다보면 N이 일정 숫자 이상일 때 부터 규칙이 있다는 것을 쉽게 알 수 있습니다.

 

2. 식 만들기

해당 문제를 동적프로그래밍으로 풀기 위해서 가장 먼저 해야할 부분은 바로 해당 문제의 점화식을 찾는 부분입니다.

해당 문제의 경우 예시에 나온 N=1 에서 N=11까지의 삼각형을 따라서 만들다 보면 N>=6일 때 부터 규칙을 찾으실 수 있습니다. 나선형을 정삼각형을 추가하여 만들기 때문에 생기는 규칙인데

 

a(N) = a(N-1) + a(N-5) (N>=6)임을 확인 할 수 있습니다.

 

여기서 N<6인 경우에는 따로 규칙이 존재하지 않으므로 배열의 N=1 에서 N=5까지의 값은 미리 채워두고 N=6부터 점화식을 이용한 동적프로그래밍 기법으로 값을 얻어나가면 쉽게 문제를 풀이할 수 있습니다.

 

3. 소스 코드

#include<iostream>

 

long long arr[101]; // 값이 int 범위를 넘어가기 때문에 long long을 사용합니다. 여러번 느끼는 부분이지만... 문제 풀이중 답이 틀린 경우 자료형 범위를 벗어나지는 않는지 꼭 한 번 확인해 봐야할 사항인 것 같습니다.

 

using namespace std;

 

int main (void) {

    int T,N;

    arr[1]=1;

    arr[2]=1;

    arr[3]=1;

    arr[4]=2;

    arr[5]=2;

    for(int i=6;i<101;i++) {

        arr[i]=arr[i-1]+arr[i-5];

    }

    cin>>T;

    for(int test=0;test<T;test++) {

        cin>>N;

        cout<<arr[N]<<endl;

    }

    return 0;

}