Algorithm
[백준 9461] 파도반 수열
moguogu
2022. 6. 17. 15:04
문제설명
테스트 케이스 수를 입력 받은 뒤, 입력되는 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 자료형을 사용했어야 했다.
자료형을 복습할 필요가 있다고 느꼈다.