[백준] 9461번 : 파도반 수열 (C언어 / C99)

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

 

 

 

조건 및 입출력

- 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

- 각 테스트 케이스마다 P(N)을 출력한다.

- 시간 제한: 1초 / 메모리 제한: 128MB

 

 

코드 (C99)

#include <stdio.h>

//전역변수 선언부
long long fibo_num[100] = { 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 };

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

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

		for (int j = 10; j <= n; j++)
			fibo_num[j] = fibo_num[j - 2] + fibo_num[j - 3];

		printf("%lld\n", fibo_num[n - 1]);
	}
	return 0;
}

 

 

---

여담

처음에 어디서 많이 본 듯한 수열이 나오길래, 어디서 봤는지 곰곰히 생각해봤다.

그러다 피보나치 수열이라는 것을 알게 되었다.

 

재귀함수를 써서 피보나치 수열을 구현하면 n=100인 경우에 너무나 오랜 시간이 걸릴 듯 하여 그냥 배열에 있는 n-2값과 n-3에 있는 값을 호출해서 값을 알아내는 방식으로 문제를 풀이했다.

 

다만, 조심해야 할 점은 n=100이므로, 값이 엄청나게 커진다.

따라서 배열의 자료형은 int형으로 지정할 경우 오버플로우가 발생하므로 long long으로 설정해야 한다.

 

 

코드가 이상하거나, 이해되지 않는 부분이 있다면 댓글 남겨주세요! + 더 좋은 풀이 방법이 있다면 알려주세요 :)