백준 9095 c++ "1, 2, 3 더하기" -PlusUltraCode-

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

[필자 사고]

동적 프로그래밍을 이용하여 문제를 해결했다.

처음에는 어떻게 접근할지 막막했지만 

1,2,3이라는 숫자를 보고 힌트를 얻었다.

dp[i] = dp[i-3] + dp[i-2] + dp[i-1] 이라는 점화식을 새워 봤는데 실제 갯수와 일치한느 모습을 볼 수 있었다.

왜 이런가 곰곰히 생각해 봤는데 dp[i-3] 입장에서는 과거의 1,2,3으로 이루어져있고 여기에 3이라는 숫자만 더 언져지만 된다.

다른 두개의 dp들도 동일한 과정이다.

아래는 상세한 코드해설이다.

 

[코드 해설]

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
int N;
vector<int> dp;

void Make_DP() {
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;

	for (int i = 4; i < 11; i++) {
		dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
	}
}

void Game_Start() {
	cin >> N;
	cout << dp[N] << '\n';
}

int main(void) {
	int T;
	cin >> T;
	dp.resize(11);
	Make_DP();

	while (T--) {
		Game_Start();
	}
}