[BOJ] 9461번 파도반 수열(C++)

풀이 소요시간 : 20분

DP 문제를 많이 풀어보지는 않았지만, 우선 주어지는 초기 값이 있다면 배열에 따로 저장하고 보는것이 좋지 않을까 하는 생각이 들었다.

void Wave() {

	DP[1] = 1;
	DP[2] = 1;
	DP[3] = 1;
	DP[4] = 2;
	DP[5] = 2;
	for (int i = 6; i <= 100; i++) {
		DP[i] = DP[i - 1] + DP[i - 5];
	}

}

그림에 보이는 삼각형이 이미 12개나 되는데, 규칙이 처음부터 보이지는 않으니 일단 5번째 삼각형까지는 DP 배열에 집어넣는 것이다. 그리고 6번째 삼각형부터 간단한 규칙을 찾아낼 수 있었다.

전체코드

#include<iostream>
using namespace std;

int T, N;
int DP[101];


void Wave() {

	DP[1] = 1;
	DP[2] = 1;
	DP[3] = 1;
	DP[4] = 2;
	DP[5] = 2;
	for (int i = 6; i <= 100; i++) {
		DP[i] = DP[i - 1] + DP[i - 5];
	}

}



int main() {

	cin >> T;
	Wave();

	for (int i = 0; i < T; i++) {
		cin >> N;
		cout << DP[N] << endl;
	}

}