728x90
반응형
9461번: 파도반 수열
문제
https://www.acmicpc.net/problem/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;
}
728x90
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
[백준 / BOJ] C++ 1065 한수 (0) | 2023.02.08 |
---|---|
[백준 / BOJ] C++ 1041 주사위 (0) | 2023.02.08 |
[백준 / BOJ] C++ 11660 구간 합 구하기 5 (0) | 2023.02.07 |
[백준 / BOJ] C++ 1037 약수 (0) | 2023.02.07 |
[백준 / BOJ] C++ 1032 명령 프롬프트 (0) | 2023.02.07 |