[백준 9461] 파도반 수열

문제설명

 

 

테스트 케이스 수를 입력 받은 뒤, 입력되는 N의 값을 출력 시키면된다.

이 때 각 값의 정의를 보자면,

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

값이 나오는 것을 확인할 수 있다.

이 값의 의미는 1번째 삼각형 일때 최대 정삼각형의 변의 길이가 1이라는 뜻이다.

즉 P(10)의 경우 10번째 삼각형을 위의 그림과 같은 규칙으로 그렸을 때 최대 정삼각형의 변의 길이가 9라는 의미이다. 

해당 값을 나열해보면 다음과 같은 점화식을 구할 수 있다.

P(N) = P(N-3) + P(N-2) 

해당 식을 이용하여 코드를 짜면 된다. 

알고리즘

1. 점화식을 이용하여 미리 답을 저장할 배열에 계산을 해서 넣어놓는다

2. 테스트 케이스를 입력받는다

3. 테스트 케이스 만큼 반복하여 배열을 조회해서 계산된 값을 출력한다 

코드

#include <iostream>
#include <stdio.h>

using namespace std;

long long result[101];
int main() {
	cin.tie(0);
	cout.tie(0);

	result[1] = result[2] = result[3] = 1;

	for (int i = 4; i <= 100; i++)//결과 값 생성
		result[i] = result[i - 2] + result[i - 3];

	int T;
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		int N;
		cin >> N;
		cout << result[N] << '\n';
	}
}

고찰

이번 문제는 점화식을 구하는 건 의외로 간단했으나 자료형을 간과하여 한번에 통과하지 못했다.

최대 100번째 삼각형일 때 까지 계산해야 했었는데, 습관적으로 int 형으로 배열을 짜서 100번째 값의 경우 음수가 출력되었다. 

따라서 int 형이 아닌 8byte를 사용하는 long long 자료형을 사용했어야 했다.

자료형을 복습할 필요가 있다고 느꼈다.

 

[참고] https://digiconfactory.tistory.com/entry/C-%EC%9D%98-%EC%9E%90%EB%A3%8C%ED%98%95-Data-type-%EC%A0%95%EC%88%98%ED%98%95