(C++) 백준 9461 파도반 수열

1. 문제

www.acmicpc.net/problem/9461

9461번: 파도반 수열

2. 풀이

초기 세팅이 많이 필요해서 헛갈릴 수 있지만 결국은 피보나치와 같은 원리이다 

삼각형의 변은 3개이기 때문에 항상 직전 것과 3개 전것의 합으로 다음 삼각형의 변이 결정된다. 

각도를 생각하면 이해하기 쉽다.

 

즉 이전의 값으로 다음의 변수가 결정되므로 이전의 값을 저장해두어야 하는 DP (Dynamic Programing)문제이다. 

 

3. 코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
	vector <long long> nums;
	nums.push_back(1);
	nums.push_back(1);
	nums.push_back(1);
	nums.push_back(2);
	nums.push_back(2); //초기환경세팅
	
	long long max = 0;
	long long n;
	cin >> n; // 테스트케이스 개수
	vector <long long> testcases;

	for (int i = 0; i < n; i++) {
		long long element;
		cin >> element;
		if (max < element) {
			max = element;
		}
		testcases.push_back(element);
	}
	for (int i = 0; i < max; i++) {
		long long next = nums[i+4] + nums[i];
		nums.push_back(next);
	}

	for (int i = 0; i < n; i++) {
		cout << nums[testcases[i] - 1]<< "\n";
	}
}

 

4. 그외 ,, 첨언

오늘부터 일주일간은 DP 문제만 주구장창 풀 예정~,~

1일 1알고리즘 시작하니 하루에 조금씩이라도 머리 써서 느낌이 좋다 ㅋㅋㅋ

화이팅