파도반 수열(Silver 3)
문제
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
접근법
파도반 수열은 다음과 같다.
1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49
파도반 수열의 규칙을 쉽게 찾을 수 있다. 임의의 위치 \(n\)에서 수열의 값을 \(f(n)\) 이라고 했을 때 \(f(n)\) 은 \(f(n-2)\) 와 \(f(n-3)\)의 합으로 이루어져 있다. 문제에서 주어진 삼각형 그림을 보면 \(f(n)\)은 \(f(n-1)\)과 \(f(n-5)\)번로 표현되어 있는데 \(f(n-1) + f(n-5)\)을 정리하면 다음과 같다.
\[f(n-1) + f(n-5)\]
\[ = [f(n-3) + f(n-4)] + f(n-5)\]
\[ = f(n-3) + [f(n-4) + f(n-5)]\]
\[ = f(n-3) + f(n-2)\]
그래서 결국 \(f(n-1) + f(n-5)\) 과 \(f(n-2) + f(n-3)\)은 동일하다. 구현의 편의를 위해서 점화식을 다음과 같이 설정하였다.
\[f(n) = f(n-2) + f(n-3)\]
구현
한번 계산된 수열의 결과가 여러번 요청될 수 있기 때문에 한번 계산한 값을 cache 배열에 저장해두어 최적화 하는 동적 계획법을 활용하자.
#include <iostream>
#include <array>
#define endl '\n'
using namespace std;
int main()
{
//입출력 성능향상을 위한 설정
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
int T; // 테스트 케이스
cin >> T;
const int Max_N = 101; // N의 최댓값
array<long long, Max_N> cache{0,1,1,};
for (int i = 3; i < Max_N; ++i)
{
cache[i] = cache[i - 3] + cache[i - 2];
}
while (T--)
{
int N;
cin >> N;
cout << cache[N] << endl;
}
return 0;
}성능 평가
시간 복잡도는 \(O(n)\) 이고 공간 복잡도 또한 \(O(n)\)임을 쉽게 확인할 수 있다.
