문제 출처

1. 문제설명

  • 정수 n이 주어질 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하라



2. 알고리즘 설계

  • DP 방식으로 풀이할 수 있다.
  • 1, 2, 3을 각각의 합으로 나타낼 수 있는 경우는 1, 2, 4가지이다.
  • 4를 1, 2, 3의 합으로 나타내는 경우의 수
    • 1 이용 : (4-1)을 만들 수 있는 경우의 수
    • 2 이용 : (4-2)을 만들 수 있는 경우의 수
    • 3 이용 : (4-3)을 만들 수 있는 경우의 수
  • 즉, 자기 자신을 뺏을 때의 경우의 수를 더해주면 된다.



3. 전체 코드

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

const int MOD = 1e9 + 9;
const int SZ = 1e6 + 1;
int TC, n, DP[SZ] = {0, 1, 2, 4};

void memoization() {
	for(int i=4; i<SZ; i++)
		for(int j=1; j<=3; j++)
			DP[i] = (DP[i] + DP[i-j]) % MOD;
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	memoization();

	cin >> TC;
	while(TC--) {
		cin >> n;
		cout << DP[n] << '\n';
	}
	
	return 0;
}