BOJ - 9095번_1, 2, 3 더하기

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램 작성하기

풀이

DP를 이용한다.

D[i] = i를 1, 2, 3의 합으로 나타내는 방법의 수를 구해야 한다.

예를 들어, D[4]는

3을 1, 2, 3의 합으로 나타내는 방법 + 1 => D[3]

2를 1, 2, 3의 합으로 나타내는 방법 + 2 => D[2]

1을 1, 2, 3의 합으로 나타내는 방법 + 3 => D[1] 이므로 D[4] = D[1] + D[2] + D[3] 임을 알 수 있다.

그러므로 점화식을 생각해보면 D[i] = D[i-1] + D[i-2] + D[i-3]이다.

소스코드

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

int d[15];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T, n;
	
	d[1]=1, d[2]=2, d[3]=4;
	for(int i=4; i<=11; i++) {
		d[i] = d[i-1] + d[i-2] + d[i-3];
	}
	
	cin >> T;
	while(T--) {
		cin >> n;
		cout << d[n] << '\n';
	}
}