알고리즘 공부 및 문제 풀이/백준(BOJ)
[c++] 9461 파도반 수열
yoonjiy
2021. 8. 4. 21:14
백준 단계별로 풀어보기 [동적계획법 1] 파도반 수열
https://www.acmicpc.net/problem/9461
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
[풀이]
파도반 수열. 1 1 1 2 2 3 4 5 7 9 12 16 ... 이 수열만 보더라도 dp[n] = dp[n-2] + dp[n-3] 이라는 점화식을 구할 수 있다. 다만, 수가 커지면 int 범위를 넘어서기 때문에 int가 아니라 long long으로 선언 해야한다.
6번째 삼각형 = 3번째(1) + 5번째(2)
7번째 삼각형 = 6번째 + 1번째(1)
8번째 삼각형 = 7번째 + 2번째(1)
9번째 삼각형 = 8번째 + 4번째(2) ...
다음의 규칙을 따라 dp[n] = dp[n-5] + dp[n-1] 의 점화식을 이용할 수도 있다.
[코드]
#include <iostream>
#include <algorithm>
long long arr[100];
int main() {
//파도반 수열
//1 1 1 2 2 3 4 5 7 9 12 16 21 28
//1 1 1 1+1 1+1 1+2 1+3 4+1 5+2 7+2 9+3 12+4 16+5 21+7
int t, n;
std::cin >> t;
arr[0] = arr[1] = arr[2] = 1;
for (int i = 0; i < t; i++) {
std::cin >> n;
for (int i = 3; i < n; i++) {
arr[i] = arr[i - 3] + arr[i - 2];
}
std::cout << arr[n - 1] << "\n";
}
}