9461번-파도반수열

문제

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

9461번: 파도반 수열

---

접근방법

1) 접근 사고

문제에서 보면 누가봐도 규칙을 찾으라고 예시까지 친절하게 준다.

2) 시간 복잡도

완전탐색으로는 구현할 방법이 떠오르지 않는 문제. 삼각형의 예시를 보면서 점화식을 찾아야 하는 문제이다.

3) 배운 점

문제에서 n은 100까지 인데 문제를 보면서 규칙을 찾다보면 점화식이 cache[n] = cache[n - 2] + cache[ n - 3]인걸 알 수 있다.

그러므로 숫자의 증가가 굉장히 빨리 이루어진져서 n이 78이 되는순간 2422362079으로 int 자료형이 넘어가므로 자료형은 반드시 long long으로 설정해줘야한다.

DP(내 코드에서 cache배열로 선언했다.)가 int 자료형을 초과하는 순간

 

4) PS

자료형 설정 잘못으로 문제를 계속 틀렸다. DP에서 숫자의 증가에 대한 맥락을 잡을 수 있었던거 같다.

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
 
ll cache[101];
int main(void)
{
    int t;
    cin >> t;
 
    cache[1] = 1;
    cache[2] = 1;
 
    for(int i = 3; i < 101; i++)
        cache[i] = cache[i - 2] + cache[i - 3];
 
    while(t--)
    {
        int n;
        cin >> n;
        if(n == 1 || n == 2)
            cout << 1 << "\n";
        else
            cout << cache[n - 2] + cache[n - 3] << "\n";
    }
}