https://www.acmicpc.net/problem/9461

걸린 시간: 6m31s

문제

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

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

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

문제 접근 방법

문제에서 주어진 수열을 살펴보면 P(n)의 값은 P(n-1) + P(n-5)라는 것을 알 수 있다.

풀이

1#include <bits/stdc++.h>
2using namespace std;
3
4#define ios cin.tie(NULL), ios_base::sync_with_stdio(false)
5#define endl '\n'
6
7typedef long long ll;
8
9int main(){
10  ios;
11  int t;
12  cin >> t;
13
14  unsigned long long p[101] = {1, 1, 1, 2, 2, 3, 4, 5, 7, 9};
15  for(int i=10; i<101; ++i) {
16    p[i] = p[i-1] + p[i-5];
17  }
18  while(t--) {
19    int v; cin >> v;
20    cout << p[v-1] << endl;
21  }
22  return 0;
23}

시간 복잡도

• 최종 시간 복잡도: O(n)

공간 복잡도

• 최종 공간 복잡도: O(n)