9461 백준 문제풀이 (C언어)

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

9461번: 파도반 수열

 

 공통적인 문제풀이는 동적계획법으로 구현을 하면 되며, 구조를 제대로 보고 규칙이 어떤 것인지 확인하면 된다.

 여기 문제에서의 규칙은 arr[N] = arr[N - 1] + arr[N - 5] 의 값인 구조인데, 배열로 값을 저장하지 않고, 아래와 같이 구현하였다. long long 으로 한 이유는 arr[N] 값이 int 의 값을 넘어 가기에 이렇게 적게되었다.

 사실 저번의 코드를 보게되니 이번 문제는 쉬웠기에 설명이 중복이 되는 거 같아 이 정도로 마무리 하겠다.

#include <stdio.h>

int main() {
	int T, num, i;
	long long temp;
	scanf("%d", &T);
	while (T <= 100 && T-- > 0)
	{
		long long arr[5] = { 1, 1, 1, 2, 2 };
		scanf("%d", &num);
		if (num <= 5)
			printf("%lld\n", arr[num - 1]);
		else {
			i = 5;
			while (++i <= num) {
				temp = arr[(i - 1) % 5] + arr[(i - 2) % 5];
				arr[(i - 1) % 5] = temp;
			}
			printf("%lld\n", temp);
		}
	}
	return 0;
}

아래는 지금 것보다는 한단계 낮은? 문제임으로 위의 코드가 이해가 안된다면 아래의 글을 보고 오면 될 거 같다.

2021.04.28 - [백준 문제풀이] - 1904 백준 문제풀이 (feat. 동적계획법)

1904 백준 문제풀이 (feat. 동적계획법)