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

#문제

9461번: 파도반 수열

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

9461번: 파도반 수열

 

---

#접근방법

규칙을 찾은 뒤 동적계획법으로 접근하였다.

반응형

---

#풀이

#include <stdio.h>

long long int dp[100] = {1,1,1,2,2};

int main(){
    int t,n;

    scanf("%d",&t);

    for(int i=5;i<100;i++)
        dp[i] = dp[i-1] + dp[i-5];

    while(t--){
        scanf("%d",&n);

        printf("%lld\n",dp[n-1]);
    }

    return 0;
}

 

정삼각형의 변의 길이가 어떤 식으로 결정이 되는지 규칙을 먼저 찾아주었다.

 

정삼각형의 변의 길이는 -1번째 변과 -5번째 변의 길이를 더한 값이라는 규칙을 발견하였다.

 

따라서 dp변수에 5개의 초기값 1,1,1,2,2를 먼저 넣어주었다.

 

그리고 5 ~ 99까지 반복문을 돌리면서 dp[i] = dp[i-1] + dp[i-5]라는 규칙을 적용시켰다.

 

이렇게 되면 n에 100을 넣으면 888855064897이라는 값이 나온다.

 

dp변수를 int 자료형을 사용하면 2^31 이라는 값이 최대값이므로 오버플로우가 생긴다. 따라서 2^63 까지 최대값으로 가질 수 있는 자료형인 long long int를 사용해주었다.

 

t만큼 반복문을 돌면서 n을 입력받고 dp[n-1]을 출력하면 정답이다.

---

#성능

---

#정리

규칙을 발견하고 적절한 자료형을 사용할 수 있으면 쉽게 풀 수 있는 문제였다.