< 백준 BaekJoon : 9461번 파도반 수열

< 백준 BaekJoon : 9461번 파도반 수열 > C++

C++/Baekjoon

by J2on 2024. 1. 27. 23:33

<< 문제 >>

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

9461번: 파도반 수열

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의

www.acmicpc.net

점화식 조건 찾기가 나름 수월합니다.

P(i) = P(i-2) + P(i-3) 으로 Dynamic Programming을 이용해서 풀면 됩니다.

<< 코드 >>

#include <iostream>
using namespace std;

void fillTable(long long*& arr){
	arr[1] = 1;
	arr[2] = 1;
	arr[3] = 1;
	for (int i = 4; i < 101; i++) {
		arr[i] = arr[i - 2] + arr[i - 3];
	}
}


int main() {

	int num;
	cin >> num;
	
	long long* arr = new long long[101];
	fillTable(arr);

	int numN;
	for (int i = 0; i < num; i++) {
		cin >> numN;
		if (numN < 4) {
			cout << 1 << '\n';
			continue;
		}
		
		cout << arr[numN] << '\n';
		
	}
	delete[] arr;
}

<< 깃헙 >>

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Silver/9461.%E2%80%85%ED%8C%8C%EB%8F%84%EB%B0%98%E2%80%85%EC%88%98%EC%97%B4

'C++ > Baekjoon' 카테고리의 다른 글

< 백준 BaekJoon : 1149번 RGB거리 > C++ (0)	2024.01.28
< 백준 BaekJoon : 1912번 연속합 > C++ (0)	2024.01.28
< 백준 BaekJoon : 1904번 01타일> C++ (0)	2024.01.27
< 백준 BaekJoon : 9184번 신나는 함수 실행> C++ (0)	2024.01.27
< 백준 BaekJoon : 14889번 스타트와 링크 > C++ (0)	2024.01.26