[BOJ] 9095번: 1,2,3 더하기

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

 

문제 풀이:

 

n=3인 경우

3

= 1+1+1

= 1+2

= 2+1

= 3 

이렇게 4가지 경우가 있다.

 

n=4인 경우

4

= 3+1 -> [n=3]인 경우에 1씩 다 더하면 된다.

= 2+2 -> [n=2]인 경우에 2씩 다 더하면 된다.

= 1+3 -> [n=1]인 경우에 3씩 다 더하면 된다.

그럼 총 7가지 경우의 수가 나온다.

 

즉, dp[n]=dp[n-1]+dp[n-2]+dp[n-3] 으로 점화식을 세울 수 있다.

 

소스 코드:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <string.h>

using namespace std;

int dp[13],n,tc;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;

	cin >> tc;
	for (int i = 0; i < tc; i++) {
		cin >> n;
		for (int j = 4; j <= n; j++) {
			dp[j] = dp[j - 1] + dp[j - 2] + dp[j - 3];
		}
		cout << dp[n] << '\n';
	}

	return 0;
}