[C] 9461: 파도반 수열

실제 파도반 수열이 뭔지는 모르겠지만

원래 수열은 모르겠으면 쓰면 되는데 이것도 그림 보면서 수열을 적다보니 쉽게 규칙이 보였다!

 

수열이 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37... 이런 식으로 증가하는데

각 수열의 항끼리 차를 통해 증가하는 값을 계산해보면

0 0 0 1 0 1 1 2 2 3 4 5 7 9... 이런 식으로 증가한다.

자세히보면 6번째부터 5개 전의 항만큼 더해지는 것을 알 수 있다.

즉., dp[i]=dp[i-1]+dp[i-5]라는 점화식을 쉽게 더해질 수 있다.

 

그리고 여기서 조심해야하는 점은 100번째 항이 int형 범위로는 표현할 수가 없어

long long int로 지정하여 문제를 풀 수 있었다.

항상 범위를 조심하고 떄에 맞는 자료형을 써야겠다.

 

여러  DP 문제들을 풀다보니 문제의 난이도를 좀 알 것같다.

1. 점화식도 쉽고 구현도 쉬운 문제

2. 점화식은 어려운데 구현은 쉬운 문제

3. 점화식을 쉬운데 구현은 어려운 문제

4. 점화식과 구현 모두 어려운 문제

 

개인적으로 느끼기에는 이 순서인데 이 문제는 1혹은 2에 해당하는 것 같다.

사실 아직 PS문제를 많이 안풀어봐서 구현하는 것을 잘 못해서 그러는 것 같긴한데

아직은 점화식이 어려운 문제가 조금 쉬운 듯한 느낌이 있다.

 

아래는 소스코드다!!

 

#include <stdio.h>

long long int dp[101];

  int main(void)
  {
    int n;
    scanf("%d",&n);
    int arr[n+1];
    for(int i=0;i<n;i++)
      {
        scanf("%d",&arr[i+1]);
      }
    dp[1]=1,dp[2]=1,dp[3]=1,dp[4]=2,dp[5]=2;
    for(int j=6;j<=100;j++)
      {
        dp[j]=dp[j-5]+dp[j-1];
      }
    for(int i=1;i<=n;i++)
      {
        printf("%lld\n",dp[arr[i]]);
      }
    
  }