[C] 백준 - 9461번: 파도반 수열

3월 8일(수) - 동적계획법 1 (9461번)

9461번: 파도반 수열

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 동적계획법 문제의 특성상, 이어지는 점화식에서 관계를 가장 먼저 찾으려고 노력했다

- P(1) = 1

  P(2) = 1

  P(3) = 1

  P(4) = 2

  P(5) = 2

  P(6) = 3

  P(7) = 4

  P(8) = 5

  P(9) = 7

 P(10) = 9

- P(6) = 3이 나왔으므로 3이 가장 빠르게 나올 수 있는 방법은 P(3) + P(4)라고 생각

- 이어지는 P(7) = 4는 P(4) + P(5) 로 표현 가능하므로 이전 P(6)에서의 계산법을 적용할 수 있음

- P(8) = P(5) + P(6) 또한 성립하므로 점화식에서의 관계라는 것이 확인됨

- 결국 P[ j ] = P[ j - 3 ] + P[ j - 2 ] 로 표현 가능

 

- 주어지는 N의 범위가 1부터 100이므로 크기가 100인 배열을 선언

- 숫자의 범위가 커질 것이 예상되므로 long long P[100] 배열을 선언

- P[4]부터 반복문을 이용해서 점화식의 관계로 값을 선언해준다

- 그 이전의 P[1], P[2], P[3] 은 모두 1로 선언

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

x

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int main(void)
{
	int T;
	scanf("%d", &T);

	for (int i = 0; i < T; i++)
	{
		int N;
		scanf("%d", &N);

		long long P[100];
		P[1] = 1;
		P[2] = 1;
		P[3] = 1;

		if (N <= 3)
		{
			printf("%lld\n", P[N]);
		}
		else
		{
			for (int j = 4; j <= N; j++)
			{
				P[j] = P[j - 3] + P[j - 2];
			}
			printf("%lld\n", P[N]);
		}
	}

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ