문제

문제 링크

해설

• 파도반 수열의 형태를 보면, 5번째 삼각형 까지(1, 1, 1, 2, 2)는 규칙성을 찾기 어렵지만, 그 뒤부터는 반드시 다른 두 삼각형과 인접한 형태이므로 변의 길이가 증가합니다.
• 이때, 인접하는 삼각형은 이전 두 삼각형입니다.
• 문제에 첫 10개의 수열이 주어지므로 DP 점화식을 구하기 조금 더 쉽습니다.
  
• DP[N] = DP[N - 3] + DP[N - 2] 점화식을 구할 수 있습니다.
• 따라서, 테스트 케이스에 진입하기 전에 미리 1부터 100까지의 모든 N에 대한 메모이제이션을 마친 후 입력받은 N에 대한 DP[N]을 단순 출력하면 됩니다.
• 주의! 이때,DP[N]은 int 범위를 넘어갑니다. 따라서 반드시 unsigned long long으로 선언해야 정답처리 받을 수 있으니 주의하도록 합시다.

코드

#include <bits/stdc++.h>
using namespace std;

unsigned long long DP[101];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int T;
	cin >> T;
	
	DP[1] = DP[2] = DP[3] = 1;
	for (int i = 4; i <= 100; ++i) DP[i] = DP[i - 3] + DP[i - 2];
	
	while (T--) {
		int N;
		cin >> N;
		cout << DP[N] << "\n";
	}
}

소스코드 링크

결과