[알고리즘] C++ 백준 9461 파도반 수열

 

백준 9461

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

9461번: 파도반 수열

풀이 전 나의 생각

삼각형이 n번째에 어떤 삼각형이 더해져서 값이 나오는지 규칙을 먼저 찾아야 한다.
 
앞서 말하자면 뭔가 쭉 나열해놓고 규칙을 찾아서 풀었는데 다른 사람들과 점화식이 달랐다.
N번째 삼각형이 만들어지기 위해선 N번째 삼각형의 변을 이루고 있는 두 삼각형 변의 길이를 더해줘야 한다고 생각했다.
그래서 되는데로 규칙을 적어봤다.
초반에 나오는 1, 1, 1은 초기값으로 생각하고 적어봤는데
(여기서 dp는 삼각형의 순번이다)
P(4) = dp[1] + dp[3]
P(5) = P(4)
P(6) = dp[1] + dp[5]
P(7) = dp[2] + dp[6]
P(8) = dp[3] + dp[7]
P(9) = dp[4] + dp[8]
P(10) = dp[5] + dp[9]
 
근데 뭔가 P(5)까지 규칙이 안맞고 P(6)부터 일정한 규칙을 나타내길래 P(5)까진 초기값을 설정해 놓고
dp[n] = dp[n - 5] + dp[n - 1] 이란 점화식을 만들어서 풀이를 진행했다. 근데 여기서 뭔가 찝찝했다.
초기값을 5번째 까지 설정해놓는게 맞나싶었다. 그래서 틀린다는 마인드로 진행했는데 잘풀렸다..
 
그래서 다른사람의 풀이를 찾아봤는데 역시나 dp[3]까지만 초기값을 넣고 이전의 삼각형 순서를 더하는 형식이었다.
ex) dp[1 ~ 3] = 1, 점화식 : DP[n - 2] + dp[n - 3]
 
무조건 인접해 있는 삼각형의 변의길이를 구해야 한다고 생각했는데 인접한 삼각형은 다른 삼각형이 대체할 수 있었다.
물론 코드에 정답은 없지만 가독성과 성능이 좋은 코드는 있다. 다음부터는 한번 더 생각해보고 풀어야겠다.
 
 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>

using namespace std;
long long tri[101];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t = 0;

	cin >> t;

	for (int i = 0; i < t; i++)
	{
		int n;
		cin >> n;

		tri[1] = 1;
		tri[2] = 1;
		tri[3] = 1;
		tri[4] = 2;
		tri[5] = 2;

		if (n < 6 || tri[n] != 0)
		{
			cout << tri[n] << '\n';
			continue;
		}

		for (int j = 6; j <= n; j++)
		{
			tri[j] = tri[j - 5] + tri[j - 1];
		}

		cout << tri[n] << '\n';
	}
}