99클럽 코테 스터디 29일차 TIL + DP(C++)

문제

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

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

 

코드

#include <iostream>
using namespace std;

int main() {
    int T, N;
    long long dp[101];

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

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

    cin >> T;

    while (T--) {
        cin >> N;
        cout << dp[N] << '\n';
    }

    return 0;
}

 

풀이

 

DP 문제.

파도반 수열에서 N번째 삼각형의 변의 길이 P(N)에 대한 규칙성을 찾아보자.

 

N = 6일 때 변의 길이: P(6) = P(1) + P(5) = 1 + 2 = 3

N = 7일 때 변의 길이: P(7) = P(2) + P(6) = 4 = 1 + 3

N = 8일 때 변의 길이: P(8) = P(3) + P(7) = 5 = 1 + 4

N = 9일 때 변의 길이: P(9) = P(4) + P(8) = 7 = 2 + 5

 

위 계산을 통해 P(N)에 대한 점화식을 P(N) = P(N - 1) + P(N - 5) 으로 정의할 수 있다.

 

단, 이 점화식은 N = 1 부터 N = 5 까지는 적용되지 않는다.

따라서 아래와 같이 dp 배열의 값을 초기화 해주어야 한다.

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

 

이후 앞에서 구한 점화식을 사용해 dp[6] 부터 dp[100] 까지의 값을 배열에 저장 후,

각 테스트 케이스마다 주어진 N에 대한 dp[N]을 출력한다.

 

주의할 점

문제에서 N의 범위는 1 ≤ N ≤ 100 으로, N = 100일 때 dp[100]은 int의 범위인 약 20억을 훨씬 초과한다.

따라서 dp 배열 생성시, 자료형을 꼭 int가 아닌 long long으로 지정해야 한다!

 

항상 경곗값을 주의하자!!