챕터3-20. DP | 문제 풀이4 - (3) 백준 No.9461 : 파도반 수열

파도반 수열 문제

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

문제요약

삼각형으로 나선을 만드는데 변의 길이가 1인 정삼각형에서 시작한다.

다음 삼각형은 지금까지 만들어진 나선에서 가장 긴 변에 정삼각형을 추가한다.
파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다.
P(1) ~ P(12) = 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12
P(N)의 값을 출력하는 프로그램을 작성해라.

해결 방법

1. D[i] 정의
생략.

 

2. 점화식 세우기

 

방법1. 직감으로 본뒤 점화식이 옳은지 확인

P(12) = 12, P(11) = 9, P(7) = 3 에서 볼 수 있듯이 P(12) = P(11) + P(7) 이다. 또한, 이러한 패턴을 다른곳에서도 보여준다.
따라서, D[i] = D[i-1] + D[i-5] 의 점화식을 세울 수 있다.

 

 

방법2. 직감으로 본뒤 점화식이 옳은지 확인 

P(12) = 12, P(9) = 5, P(10) = 7 에서 볼 수 있듯이 P(12) = P(10) + P(9) 이다. 또한, 이러한 패턴을 다른곳에서도 보여준다.
따라서, D[i] = D[i-2] + D[i-3] 의 점화식을 세울 수 있다.

<Bottom-up 방식>

 

* overflow때문에 long long 형으로 해줘야 한다.

 

(1)시간복잡도
= for 문의 반복 횟수 

 

(2) 구현
-> 'for문을 이용한 반복문'으로 구현

/*방법1*/
#include <iostream>

using namespace std;

long long d[101];

int main()
{
    int T;
    cin >> T;

    while(T--){
        int n;
        cin >> n;

        d[1] = 1;
        d[2] = 1;
        d[3] = 1;
        d[4] = 2;
        d[5] = 2;

        for (int i = 6; i <= n; i++)
            d[i] = d[i - 1] + d[i - 5];

        cout << d[n] << "\n";
    }
}

/*방법2*/
#include <iostream>

using namespace std;

long long d[101];

int main()
{
    int T;
    cin >> T;

    while(T--){
        int n;
        cin >> n;

        d[1] = 1;
        d[2] = 1;
        d[3] = 1;

        for (int i = 4; i <= n; i++)
            d[i] = d[i - 2] + d[i - 3];

        cout << d[n] << "\n";
    }
}