BOJ 백준 9461 파도반 수열

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

< 파도반 수열 >

1 1 1 2 2 3 4 5 7 9 12 ...

12의 다음은 문제 그림에 있는 밑면, 12 + 4인 16이 나온다.

16의 다음은 밑면에 거꾸로 된 삼각형이 붙어있다고 생각하면, 왼쪽 면인 16 + 5로 21이 나오게된다.

1 1 1 2 2 3 4 5 7 9 12 16 21...

가장 가까이 있는 항으로 규칙을 맞춰보려면, 21 = 16 + 5 // 16 = 12 + 4, 즉 dp[n] = dp[n - 1] + dp[n - 5]가 된다.

dp[n] = dp[n-1] + dp[n-5]로 하기 위해서는, 1 1 1 2 2 를 내가 직접 넣어주고, 6번째항부터 점화식이 성립된다. 

즉, 기본값으로 5개가 있어야하는 것이다.

프로그램이 아닌 자신이 직접 답을 계산해서 넣어주어야 하는 값이 많다는 것은, 좋은 문제풀이가 아닐 것이다.

문제로 돌아와 다시 보니, 21 = 12 + 9 // 16 = 9 + 7 로도 구할 수 있다. 즉, dp[n] = dp[n - 2] + dp[n - 3]이 성립한다.

이번 점화식은, dp[1] = dp[2] = dp[3] = 1 로 첫 3번째 항까지만 기본값으로 넣어주면, 4번째항부터 프로그램이 계산할 수 있다.

dp[n] = dp[n - 1] + dp[n-5]로 풀이한 것과 dp[n] = dp[n-2] + dp[n-3]으로 풀이한 것 모두 정답처리가 되긴 한다.

N의 조건이 100 이하이므로, 100까지 모두 구해준 뒤, scanf로 받아오는 항의 값을 바로 출력해주어도 된다.

나는 연산의 횟수를 사용자가 입력한 만큼만 해주고 싶어서, 따로 idx란 변수를 두어 입력받은 n만큼만 구하도록 해보았다.

#include <cstdio>
#define SIZE 101

long long dp[SIZE];

int main(){
	dp[1] = dp[2] = dp[3] = 1;
	int idx = 4;
	 
	int t, n; 
	scanf("%d", &t);
	while(t--){
		scanf("%d", &n);
	
		for(idx; idx <= n; idx++){
			dp[idx] = dp[idx - 2] + dp[idx - 3];
		}
		printf("%lld\n", dp[n]);	
	}
	
	return 0;
}