[백준 9461] 파도반 수열

문제 : 파도반 수열

문제 유형 : 다이나믹 프로그래밍

이 문제는 규칙을 찾기만 하면 되는 문제이다.

난 두가지 점화식으로 풀었다.

1. 점화식1

일단 가장 먼저 풀었던 방식을 설명하자면, 소용돌이처럼 이어지는 수를 한 줄로 써보았다.

1 1 1 2 2 3 4 5 7 9 12 ...

이것을 보고 규칙이 바로 보였다. 지금 현재 위치에서 왼쪽으로 2칸 떨어진 것과 같은 방향으로 3칸 떨어진 것의 합이 현재 위치의 값과 같다는 점화식을 발견했다. 이를 식으로 쓰자면 아래와 같다.

이 식을 가지고 초기값만 잘 넣어주면 쉽게 맞추는 문제이다. 또한 n이 커지면 int형의 범위가 벗어나니 맞왜틀 했던 사람들은 int를 long long으로 바꿔보기 바란다.

- 소스코드

#include<iostream>
 
using namespace std;
typedef long long ll;
 
ll dp[5000];
 
ll solve(int n)
{
    if (n <= 1)return n;
    else if (dp[n])return dp[n];
    else return (dp[n] = solve(n - 2) + solve(n - 3));
}
 
int main()
{
    dp[1] = dp[2] = 1;
    int t;
    cin >> t;
    for (; t--;) {
        int n;
        cin >> n;
        cout << solve(n) << '\n';
    }
    return 0;
}

2. 점화식2

사실 그림을 잘 보면 규칙이 바로 나오는 문제이다. 그림을 잘 보면 큰 삼각형의 한 변에 닿아있는 두 삼각형 내부에 써져 있는 숫자의 합은 큰 삼각형 안에 있는 값과 동일한 것을 알 수 있다. 그림에서 9를 가지고 점화식을 세워보자. 

9가 나오는 방법은 그 전에 있던 삼각형과 5번째 전에 있던 삼각형의 합으로 나오는 것을 알 수 있다. 그러면 아래와 같이 세울 수 있다.

이것도 초기값을 잘 넣으면 쉽게 맞출 수 있다.

#include<iostream>
 
using namespace std;
typedef long long ll;
ll dp[1000] = {0,1,1,1,2,2,};
 
ll solve(int n)
{
    if(dp[n])return dp[n];
    else return dp[n] = solve(n-1) + solve(n-5);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t, n;
    cin >> t;
    while(t--){
        cin >> n;
        cout << solve(n) << '\n';
    }
    return 0;
}