[백준/C++] 알고리즘 9146번 - 파도반 수열

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 9146번 - 파도반 수열을 풀어보도록 하겠습니다.

 

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

9461번: 파도반 수열

 

[문제 접근]

반복성이 보이고, 패턴을 발견할 수 있다는 생각을 가지고 다이나믹 프로그래밍으로 접근했습니다.

이미 문제에서 점화식의 정의를 주어졌기 때문에 점화식만 구하면 됩니다.

p[i] = p[i-1] + p[i-5]임을 찾아낼 수 있습니다.

 

[풀이 전략]

1. p[1] ~ p[5]까지 초기값을 설정합니다.

2. p[i] = p[i-1] + p[i-5] 점화식을 이용하여 p[6],,,p[n]까지 순차적으로 구합니다.

3. p[n]을 출력합니다.

 

[코드]

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


int n,t ; 
long long  p[101];
int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 

    p[1] = 1 ;
    p[2] = 1 ;
    p[3] = 1 ;
    p[4] = 2 ;
    p[5] = 2 ;

    for(int i = 6 ; i <= 100 ; i++) {
        p[i] = p[i-1] + p[i-5];
    }


    cin >> t ;

    while (t--)
    {
        cin >> n ;
        cout << p[n] <<'\n';
    }
    
 
}

 

[배울 점]

- 초기에 규칙성이 발견되지 않을 수 있으니, 수를 조금 더 늘려서 상황 관찰하기.