[백준] 9461번: 파도반 수 (C언어)

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

9461번: 파도반 수열

난이도: solved.ac 실버 3

 

그림이 있어 규칙찾기 매우 쉬운 dp문제다

N번째 삼각형 변의 길이를 tri[N]이라고 해보자

 

그림을 자세히보면

tri[6]부터는 바로 앞 삼각형인 tri[N-1]의 변과 tri[N-5] 변이 한 변이 되는 걸 알 수 있다

tri[N] = tri[N-5] + tri[N-1]     (N ≥ 6)

tri[1]부터 tri[5]까지는 각 값을 지정해주고 (tri[0]은 그냥 0으로 비워두었다)

tri[6]부터는 위의 점화식으로 나타내주었다

 

그리고 주의할 점!

 

배열을 선언할 때 int형으로 하면 안된다

 

N = 100일 때 보면 매우 큰 수가 되는데 int형으로는 나타내지 못해서

 

난 long long int로 선언해주었다

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

long int tri[101] = { 0,1,1,1,2,2 };    // tri[5]까지 초기화

int main() {
    int T, N, t, i;
    scanf("%d", &T);
    for (t = 0; t < T; t++) {
        scanf("%d", &N);
        for (i = 6; i <= N; i++)
            tri[i] = tri[i - 5] + tri[i - 1];
        printf("%ld\n", tri[N]);
    }
	return 0;
}