[BaekJoon 9461][⚪3] 파도반 수열

❓ 문제

백준 9461 - “파도반 수열”

🎯 난이도

Silver ⚪3

🧠 풀이

1. 내 풀이 (DP)

- 알고리즘

• Mathematics, Dynamic Programming

- 설명

DP 알고리즘을 사용해 푸는 방식이다.

이 파도반 수열이라고 하는 삼각형들의 나열 방식을 잘 보면, 규칙이 있다. 'i'번째 삼각형의 한 변은 'i - 5'번째 삼각형과 'i - 1'번째 삼각형의 변과 맞닿아 있다는 것이다. 따라서 이 규칙을 사용하면, 다음과 같은 점화식이 나오게 된다.

\[dp[i]=dp[i-5]+dp[i-1]\]

이 식을 사용해서 초기값을 잘 넣어주고, 식에 맞게 DP 배열을 채워주면 끝이다.

입력값에 따라 DP 배열을 N까지의 루프를 돌며 채우므로, 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>

#include <algorithm>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iT{};
    cin >> iT;

    vector<int> vecNum(iT); // 입력값 저장 벡터
    int iMax{}; // 입력값의 최대값을 저장할 변수

    for(int& iNum : vecNum)
    {
        cin >> iNum;
        iMax = max(iMax, iNum);
    }

    vector<long long> vecDP(max(5, iMax) + 1);  // DP 배열
    // 초기값 넣어줌
    vecDP[1] = vecDP[2] = vecDP[3] = 1;
    vecDP[4] = vecDP[5] = 2;

    for(int i = 6; i <= iMax; ++i)
    {
        // 점화식에 맞게 계산해서 DP 배열 채움
        vecDP[i] = vecDP[i - 5] + vecDP[i - 1];
    }

    for(int iNum : vecNum)
    {
        // 입력값에 맞는 DP 값 출력
        cout << vecDP[iNum] << '\n';
    }

    return 0;
}

---

💭 후기

나는 개인적으로 기하학적 관점에서 접근해 삼각형들의 나열 규칙을 찾아 점화식을 세워 풀었지만, 사실 이 파도반 수열이라는 것은 원래 존재하는 수열이고, 이미 따로 증명이 된 점화식도 있다고 한다. 물론 미리 알았으면 더 쉽게 풀었겠지만, 아예 모르는 관점에서 보더라도 풀이를 도출해내기엔 그리 어렵지 않은 문제였던 것 같다.

🔗 참고자료

• 파도반 수열