[ 백준 9461 ] 파도반 수열 (C++)

백준의 파도반수열(9461) 문제이다.

( 문제 바로가기 )

( 문제를 다시 푸는 과정에서 아래의 글과는 다른 방법으로 그리고 보다 구체적으로 다시 포스팅 하였습니다.

  아래의 글을 읽고 문제를 푸셔도 무관하지만 더욱 구체적인 풀이를 원하시는 분들은 아래의 링크를 참고해주세요.

  [ 파도반 수열 (9461) 풀이 바로가기 ]

[ 문제풀이 ]

1. 일반 문제에 보면 무슨 삼각형 그림이 있는데 솔직히 뭔지 잘 모르겠다. 그냥 저런식으로 변이 증가하면서 만들어진 삼각형을

   파도반 수열이라고 하는 것 같다.

2. 입력으로 주어지는 숫자가 P(N)으로 얼마의 값인지 구하는 것이 문제인데, 여기서 P(N)이라는 것은 위에서 말한 증가하는 수열의

   N번째 숫자를 의미한다.

3. 규칙을 찾아보자. 1 -> 1-> 1 -> 2 -> 2-> 3-> 4-> 5-> ... 이런식으로 증가하는데...

   보면 N번째 값은 N-2번째 값과 N-3번째 값을 더한 값이라는 것을 알 수 있다.

   ( 다른 분들의 풀이법을 봤을 때는, N-1번째 값과 N-5번째 값을 더했다고 많은 풀이들이 있는데 솔직히 그분들 풀이 안봤으면

     나는 그 규칙 못찾았을 것 같다 )

   무튼 내가 찾은 규칙을 저렇다. 하지만 평소와 같이 제출을 했더니 틀렸습니다 가 떴다.

   이유를 찾아보면... N의 최댓값이 100이라고 주어져있는데, 100을 넣을 경우 int형의 범위가 초과된다. 약 8천9백억 정도의 값이

   나온다. 그래서 int형이 아닌 long long 자료형으로 선언해 봤떠니 해결할 수 있었다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
typedef long long ll;
#define endl "\n"
#define MAX 100 + 1
using namespace std;
 
ll DP[MAX];
int N;
 
void Initialize()
{
    memset(DP, 0, sizeof(DP));
}
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    DP[0] = 0;
    DP[1] = 1;
    DP[2] = 1;
    for (int i = 3; i <= N; i++)
    {
        DP[i] = DP[i - 2] + DP[i - 3];
    }
    cout << DP[N] << endl;
}
 
void Solve()
{
    int Tc;
    cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}