[BOJ/C++]9461번 파도반 수열

www.acmicpc.net/problem/9461

9461번: 파도반 수열

---

문제

정삼각형이 나선 모양으로 추가되었을 때, 처음부터 추가되는 정삼각형 변의 길이의 수열을 파도반 수열이라고 함.

첫 10개 숫자는 1,1,1,2,2,3,4,6,7,9

N이 주어졌을 때 P(N)을 구하는 프로그램

 

풀이

처음에 점화식을 잘못 구해 고생했던 문제.

나 같은 경우에는 문제를 제대로 안 읽고 위에서 나열한 숫자의 일부(4까지)만 보고 P(n)=P(n-2)+P(n-3)으로 생각했다.

문제에서 준 예시 아래의 그림을 보면

3까지, 즉 6번째 경우를 제외하고 그 이후부터는 p(n)=p(n-1)+p(n-5)의 규칙대로 삼각형 변의 길이가 증가하는 것을 알 수 있다. 따라서 이 점화식을 활용해 DP를 이용해 풀면 쉽게 풀 수 있는 문제.

지만

나는 DP 배열을 int로 지정했다가 계속 틀렸습니다 떠서 애먹었다.

DP배열을 long long으로 했더니 성공.

소스코드

#include<iostream>
#include<algorithm>
using namespace std;

int main(void){
    int T;
    cin>>T;
    
    long long dp[101]={0,1,1,1,2,2, };
    for(int i=6;i<101;i++){
        dp[i]=dp[i-1]+dp[i-5];
    }

    for(int i=0;i<T;i++){
        int n;
        cin>>n;
        cout<<dp[n]<<endl;
    }

}

 

아래는 내가 실패했던 코드들 몇 가지..

#include<iostream>
using namespace std;

int main(void){
    int T;
    cin>>T;
    for(int testcase=0;testcase<T;testcase++){
        int n;
        cin>>n;
        int dp[n+1];
        dp[1]=1;dp[2]=1;dp[3]=1;
        for(int i=4;i<n+1;i++){
            dp[i]=dp[i-3]+dp[i-2];
        }
        cout<<dp[n]<<endl;
    }
}

#include<iostream>
#include<algorithm>
using namespace std;

int main(void){
    int T;
    cin>>T;
    int num[T]; int n=0;
    for(int i=0;i<T;i++){
        cin>>num[i];
        n=max(n,num[i]);
    }
    int dp[n+1];
    dp[1]=1;dp[2]=1;dp[3]=1;
    for(int i=4;i<n+1;i++){
        dp[i]=dp[i-3]+dp[i-2];
    }

    for(int i=0;i<T;i++){
        cout<<dp[num[i]]<<endl;
    }
}

#include<iostream>
#include<algorithm>
using namespace std;

int main(void){
    int T;
    cin>>T;
    
    int dp[101]={0,1,1,1,2,2, };
    for(int i=6;i<101;i++){
        dp[i]=dp[i-1]+dp[i-5];
    }

    for(int i=0;i<T;i++){
        int n;
        cin>>n;
        cout<<dp[n]<<endl;
    }

}