[C언어] 백준 9461 : 파도반 수열

생각의 흐름

쉽겠다 피보나치마냥 동적계획법 써서 다 저장하고 뽑아내면 끝이겠구나

당연히 문제에는 규칙이 있을 것이고 재귀를 사용해서 저장해야겠다.

문제를 보니 arr[n] = arr[n - 5] + arr[n - 1] 이란 규칙이 있다. n = 1 ~ 5까지 각각의 수를 저장해놓고 n = 6부터 저장해가면 되겠구나 싶었다.

딱 여기까지 생각하고 코드 작성했다.

내가 푼 코드

#include <stdio.h>

long long arr[101] = {0, 1, 1, 1, 2, 2, };

long long dp(int n)
{
	if (n <= 3)
		return 1;
	else if (n <= 5)
		return 2;
	else if (arr[n] == 0)
		arr[n] = dp(n - 5) + dp(n - 1);
	return arr[n];
}

int main()
{
	int t, n;
	scanf("%d", &t);
	int i = 0;
	while(i < t)
	{
		scanf("%d", &n);
		dp(n);
		printf("%lld\n", arr[n]);
		i++;
	}
}

n값이 일정 숫자가 넘어가면 오버플로우가 일어난다. 그래서 arr에 longlong처리해주었고, dp함수에도 그렇게 해주었다.

다른 사람 코드

#include <iostream>

using namespace std;
long long arr[101] = { 1,1,1, };

long long p(int n) {
	if (n == 1 || n == 2 || n == 3) return arr[n - 1];
	else if (arr[n - 1] == 0) arr[n - 1] = p(n - 3) + p(n - 2);
	return arr[n-1];
}

int main() {
	int t, tmp;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> tmp;
		cout << p(tmp) << "\n";
	}
}

규칙을 n = (n - 3) + (n - 2)로 했다. 똑같다. 여기도 재귀로 진행을 했다.

다음에 이런게 또 나오면 그냥 반복문으로 풀어야겠다 귀찮아졌다.

아니다 그냥 번갈아가면서 사용하자.