문제
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 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)을 출력한다.
풀이
파도반 수열은 앞의 두세 항이 단순히 더해지는 피보나치와 조금 다르다. 현재 구현은 문제에서 주어진 규칙에 맞춰 필요한 이전 항만 이용해 DP로 수열을 채운다.
작은 항들을 기저로 잡아 두고, 그 이후 값은 정해진 간격의 이전 항을 더해 만든다. 테스트케이스가 여러 개라도 한 번 채워 두면 바로 답을 꺼낼 수 있다.
결국 수열 문제의 핵심은 점화식을 정확히 읽어 내는 것이다. 어떤 이전 항이 필요한지만 보이면 구현은 어렵지 않다.
코드
#include <iostream>
using namespace std;
void solve() {
int t, n;
cin >> t;
long long arr[101] = {};
arr[0] = arr[1] = arr[2] = 1;
arr[3] = arr[4] = 2;
for (int i = 5; i < 101; i++)
arr[i] = arr[i - 5] + arr[i - 1];
while (t--) {
cin >> n;
cout << arr[n - 1] << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}복잡도
- 시간 복잡도: 필요한 항까지 파도반 수열을 채우므로 이다.
- 공간 복잡도: DP 배열을 저장하므로 이다.
마무리
파도반 수열은 바로 앞이 아니라 조금 떨어진 항들이 이어진다는 점만 잡으면 된다.
