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

9461번: 파도반 수열 (acmicpc.net)

9461번: 파도반 수열

---

규칙성을 찾는 게 중요한 다이나믹 프로그래밍 유형,,

1, 1, 1, 2, 2, 3, 4, 5, 7, 9

점화식을 세워보면 

 

P(1) = 1

P(2) = 1

P(3) = 1

n>3일 때, P(n) = P(n-3) + P(n-2) 

 

또,, 가장 쉽게 생각할 수 있는 재귀 방법으로 풀었는 데 시간 초과가 떴다

 

#include <iostream>

using namespace std;

int pado(int n) {
    if(n==1 | n==2 | n==3){
        return 1;
    }
    
    return pado(n-3) + pado(n-2);
}

int main()
{
    int t, n;
    cin >> t;
    
    for(int i=0; i<t; i++){
        cin >> n;
        
        cout << pado(n) << "\n";
    }
    
    
    
    return 0;
}

[백준] 9461 파도반 수열 C++ (DP) (velog.io)

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

 

문제였던 부분이

 

1. long long의 자료형을 써야한다는 것

2. 재귀를 사용하지 말고 dp를 써야 함

3. d[N] = d[N-5] + d[N-1] 를 사용해야함

 

그렇게 수정된 코드는!

#include <iostream>

using namespace std;

int main()
{
    int t, m;
    long long n[101] = {1, 1, 1, 2 , 2 ,};
    
    for(int i=5; i<101; i++){
        n[i] = n[i-1] + n[i-5];
    }
    
    cin >> t;
    
    for(int i=0; i<t; i++){
        cin >> m;
         cout << n[m-1] << "\n";
    }
    
    
    
    return 0;
}