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

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

9461번: 파도반 수열

 

 

 

 

---

- 문제

 

  피보나치 수열과 비슷한 형태의 문제를 해결하는 문제다. 다만, n-1 + n-2가 아니라 n-2 + n-3이다.

 

 

---

- 해설

 

메모이제이션과 피보나치 수열의 변형을 이용해서 풀면된다.

 

신경써야 할 점으로는 

 

 - 시간 초과

 

 - 자료형

 

이 있다.

 

메모이제이션 없이 dfs 느낌으로 풀면 시간초과가 날 수 밖에 없고,

 

피보나치 수열과 같은 형태의 문제는 n이 100까지만 가더라도 int 자료형으로는 감당할 수 없는 숫자가 나오므로 long이나 long long과 같은 형태를 염두해 두어야 한다.

 

 

 

 

---

- 풀이

#include <iostream>
using namespace std;

// else if 말고 else로 했을때 시간초과, long말고 int 했을 때 틀림, 피보나치 수열처럼 증가하게 되면 100까지 가더라도 기하급수적으로 증가하므로, long이나 long long 필요!!!

long triangleMemo[101] = {
    0,
    1,
    1,
};

long triangleLength(int n)
{
    if (n < 3)
    {
        return triangleMemo[n];
    }
    else if (triangleMemo[n] == 0)
    {
        triangleMemo[n] = triangleLength(n - 2) + triangleLength(n - 3);
    }
    return triangleMemo[n];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, temp;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> temp;
        cout << triangleLength(temp) << '\n';
    }
    return 0;
}

 

 

---

- 새롭게 알게 된 점