백준 9461번

9461번은 다이나믹 프로그래밍을 이용하는 문제이다. 그래서, 우선 그림을 보고 그에 대한 점화식을 찾아보았다. 그 결과, 5번째 삼각형까지는 규칙이 없지만, 그 이후의 삼각형들의 변의 길이는 다음과 같은 점화식을 따른다는 것을 알게 되었다:

x가 삼각형의 길이를 담은 배열이고, n이 삼각형의 번째 수라고 한다면, 
x[n] = x[n - 1] + x[n - 5];

이 규칙을 그대로 이용해서, 코드를 짜주면 끝이다. 다만, n의 범위가 100번까지고, 끝까지 간다면 int의 범위를 넘게 된다. 그래서, 배열 변수의 타입을 int가 아닌 long long으로 해주는 것을 주의해야 한다.

#include <stdio.h>

int main(void) {

	long long array[101] = { 0, 1, 1, 1, 2, 2 };
	int total;
	scanf("%d", &total);
	int num;
	for (int i = 6; i < 101; i++) {
		array[i] = array[i - 1] + array[i - 5];
	}
	for (int i = 0; i < total; i++) {
		scanf("%d", &num);
		printf("%lld\n", array[num]);
	}
	return 0;
}