[백준/C/Python] 9461 - 파도반 수열

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

구현 과정

수열의 규칙만 구하면 쉽게 풀 수 있는 문제다. 직접 그림을 그려가며 10번째쯤까지 해보면, P(n)의 값은 두 값을 더해서 나오는 숫자라는 것을 알 수 있다.

표로 정리해보면 아래와 같다. P(6)부터 P(n) = P(n-1) + P(n-5) 라는 규칙이 보인다.

따라서 P(5)까지 미리 초기화해두고, P(6)부터 for문을 돌면서 값을 채워나가면 된다. P(n) 값들이 매우 큰 숫자가 나올 수 있기 때문에 C로 구현하는 경우 long long 자료형을 사용해야 한다.

전체 코드

C

#include <stdio.h>

long long dp[101];

void padoban() {
    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];
    }
}

int main() {
    int t;
    scanf("%d", &t);

    padoban();

    while (t--) {
        int n;
        scanf("%d", &n);
        printf("%lld\n", dp[n]);
    }
    return 0;
}

Python

def padoban():
    dp = [0] * 101
    dp[1] = 1
    dp[2] = 1
    dp[3] = 1
    dp[4] = 2
    dp[5] = 2

    for i in range(6, 101):
        dp[i] = dp[i - 1] + dp[i - 5]
        
    return dp

t = int(input())

dp = padoban()

for _ in range (t):
    n = int(input())
    print(f"{dp[n]}")