백준 9461번 [파도반 수열](C++) -yes6686- 티스토리

백준 문제 풀이: 9461 [파도반 수열]

---

문제 링크: https://www.acmicpc.net/problem/9461

문제 설명:

파도반 수열은 다음 점화식을 따릅니다:

• P(1) = 1, P(2) = 1, P(3) = 1
• P(n) = P(n-1) + P(n-5) (n ≥ 4)

여러 개의 테스트 케이스에서 주어진 n에 대해 P(n)을 계산하는 문제입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

long long dp[101]; // 파도반 수열 값 저장

int main() {
    int T;
    cin >> T;

    // 초기값 설정
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 1;
    dp[4] = 2;

    // 점화식에 따라 나머지 값 계산
    for (int i = 5; i <= 100; i++) {
        dp[i] = dp[i - 1] + dp[i - 5];
    }

    // 테스트 케이스 처리
    while (T--) {
        int n;
        cin >> n;
        cout << dp[n] << '\n'; // 결과 출력
    }

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 점화식을 기반으로 DP 배열을 미리 계산해놓고 각 테스트 케이스마다 빠르게 결과를 출력합니다.
• 구현 세부사항:
  • dp[i]: P(i) 값을 저장
  • 점화식: dp[i] = dp[i - 1] + dp[i - 5] (i ≥ 5)
  • 테스트 케이스에서 입력된 n에 대해 dp[n]을 출력
• 시간 복잡도 분석: O(100 + T)
  • DP 배열을 미리 계산하는 데 O(100)
  • T개의 테스트 케이스에서 결과를 출력하는 데 O(T)

---

결과

주어진 n에 대해 파도반 수열의 값을 정확히 계산하고 출력합니다. DP를 사용하여 효율적으로 문제를 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!