C++ 백준 15988번

계속 다이나믹 프로그래밍 연습중이다!!

 

백준 15988번 www.acmicpc.net/problem/15988

15988번: 1, 2, 3 더하기 3

문제 : 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

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

 

정수 n을 1, 2, 3의 합으로 나타낼 수 있으니까 d[n] = d[n-1] + d[n-2] + d[n-3]으로 점화식을 사용할 수 있다.

d[n-1] 은 맨 마지막에 1을 더해주는 합의 경우의 수, d[n-2]는 맨 마지막에 2를 더해주는 경우의 수, d[n-3]은 맨 마지막에 3을 더해주는 경우의 수이다!!

#include<iostream>
using namespace std;
long long mod = 1000000009;
long long d[1000001];
long long go(int n) {
	d[0] = 0;
	d[1] = 1;
	d[2] = 2;
	d[3] = 4;
	if (d[n] > 0) return d[n];
	d[n] = (go(n - 1) + go(n - 2) + go(n - 3)) % mod;
	return d[n];
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		cout << go(n) << '\n';
	}
}