[백준 / BOJ] C++ 9461 파도반 수열

9461번: 파도반 수열

 

문제

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

9461번: 파도반 수열

 

 

풀이

한 변의 길이가 1인 정삼각형으로 시작해 도형의 가장 긴 변의 길이를 한 변의 길이로 하는 정삼각형을 추가해가며 N번째 정삼각형의 한 변의 길이를 P(N)이라 하고 이를 출력하는 문제.

 

1번 풀이

P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

라는 문제 본문을 읽고 가장 먼저 [1, 1, 1]로 시작하며 i번째 항은 i-2번째 항과 i-3번째 항의 합이라는 생각을 했다. 따라서 dp 배열을 만들어 N번째 항까지 구하고 출력하도록 구현했고 맞았다.

 

2번 풀이

추가로 다른 풀이는 [1, 1, 1, 2, 2]로 시작해서 i번째 항은 i-1번째 항과 i-5번째 항의 합으로 나타내는 방법도 있다.

 

 

코드 (1번 풀이)

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<long long> dp(n, 0);
    dp[0] = 1, dp[1] = 1, dp[2] = 1;
    for (int i = 3; i < n; i++)
      dp[i] = dp[i - 2] + dp[i - 3];
    cout << dp[n - 1] << '\n';
  }
  return 0;
}

 

코드 (2번 풀이)

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<long long> v{1, 1, 1, 2, 2};
    for (int i = 0, j = 4; v.size() < n; i++, j++)
      v.push_back(v[i] + v[j]);
    cout << v[n - 1] << '\n';
  }
  return 0;
}