C++ / 9461 / 파도반 수열 ( 다이나믹 프로그래밍 )

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

문제 요약

그림과 같이 삼각형이 나선 모양으로 놓여져 있습니다. 첫 삼각형은 정삼각형으로 변의 길이는 1입니다.

그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가합니다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가합니다.

 

파도반 수열 p(n)은 나선에 있는 정삼각형의 변의 길이입니다. p[1]부터 p[10]까지 첫 10개의 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 입니다.

n이 주어졌을 때, p(n)을 구해야합니다.

문제 풀이

1. 케이스 개수를 입력 받습니다.

2. 입력 받은 케이스 만큼 원하는 숫자를 입력 받습니다.

3. dp함수를 만들어 정답 배열을 만드는데,  정답 배열에 초기 값으로 0번째 부터 2번째까지 값을 넣어줍니다.

4. 삼각형이 생길때 변이 늘어나는 규칙은 전전항 변의 길이 + 전항 변의 길이 = 현재항 변의 길이 이기 때문에

p[ i ] = p[ i - 2 ] + p[ i - 3 ]

정답 배열을 초기화 해줍니다.

5. 입력 받은 원하는 숫자별로 정답 배열에 인덱스에 넣고 정답을 출력합니다.

주의할 점

요즘 dp문제 위주로 풀어보는 중입니다.

이 문제는 dp문제들 중 쉬운편에 속합니다. 다만 p(n)의 값이 int를 넘어가는 경우가 생기기 때문에 long long int를 사용하는 것이 중요합니다.

코드

#include<iostream>
#include<vector>

using namespace std;

long long int p[101];
vector<int>v;

long long int t, n;

void dp()
{
	p[0] = 0;
	p[1] = 1;
	p[2] = 1;
	for (long long int i = 3; i <= 100; i++)
	{
		p[i] = p[i - 2] + p[i - 3];
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> t;
	for (long long int i = 0; i < t; i++)
	{
		cin >> n;
		if (n <= 0)
		{
			return 0;
		}
		v.push_back(n);
	}
	dp();
	for (long long int i = 0; i < v.size(); i++)
	{
		cout << p[v[i]] << "\n";
	}
	return 0;
}

반응형

예제

2
6
12

결과