[백준 9461] 파도반 수열

문제

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

9461번: 파도반 수열

 

 

문제 분석

우측에 있는 그림처럼 생긴 그림이 있고, 입력 받은 수의 번째에 생성된 삼각형의 크기가 몇인지 출력하는 문제이다. 

 

 

알고리즘 설계

우선 테스트 케이스의 개수를 담을 t와 테스트 케이스를 담을 n을 int형으로 선언한다. 

 

n이 100 이하로 나오기에 longlong을 가지고 있을 vector을 하나 만들고 크기를 101로 만들어준다. 

이후 1, 2, 3번 인덱스는 1로 초기화 시켜준다. 

 

이후 for을 사용하여 4부터 100까지 반복 시켜주고, 

i번째의 값을 vec의 i-2값과 vec의 i-3값을 넣어준다. 

 

t를 입력 받고, t의 횟수만큼 반복문을 돌린다. 

반복문 안에서 n을 입력받고, vec의 n번째 인수를 출력한다. 

 

 

유의점

값을 담아둘 공간은 long long으로 해주어야한다. 

 

 

코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int t,n;
	vector<long long> vec(101);

	cin >> t;
	
	vec[1] = vec[2] = vec[3] = 1;
	for (int i = 4; i < 101; ++i)
		vec[i] = vec[i - 2] + vec[i - 3];

	while (t--)
	{
		cin >> n;
		cout << vec[n] << '\n';
	}
}