[백준] 알고리즘 9095번 - 1, 2, 3 더하기 문제

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

9095번: 1, 2, 3 더하기

소스코드

#include <bits/stdc++.h>
using namespace std;
long long dp[1000001];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T,mod=1000000009;
	cin >> T;
	dp[1] = 1, dp[2] = 2, dp[3] = 4;
	while (T--) {
		int n;
		cin >> n;
		for (int i = 4; i <= n; i++) {
			dp[i] = (dp[i - 3] + dp[i - 2] + dp[i - 1])%mod;
		}
		cout << dp[n] << "\n";
	}
}
 

풀이

동전 문제와 비슷하게 접근하여 해결 해보았습니다.

먼저 1원짜리로만 N까지 만들 수 있는 경우의 수는 1입니다.

그리고 2원짜리를 최소 한개 이상 사용하여 만들 수 있는 경우의 수

그리고 3원짜리를 최소 한개 이상 사용하여 만들 수 있는 경우의 수

이런식으로 표를 구성하여 작성한 후에 2차원 배열로 접근하려 했으나 1차원 배열로도 충분히 점화식을 세울 수 있습니다.

N원을 만들 수 있는 수의 개수는 1,2,3 원짜리 최소 한 개씩 사용하여 만들어야 하기 때문에 합계를 출력해줘야 한다.

여기서 우리는 규칙을 찾을 수 있다.

DP[N] = DP[N-3] + DP[N-2] + DP[N-1]