[DP #22] (BOJ 15990) 1,2,3 더하기 5

https://www.acmicpc.net/problem/15990

15990번: 1, 2, 3 더하기 5

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

---

접근법

1차 시도

DP[i] = DP[i]번째까지 가지수로 두고 문제에 접근했다.

만약 DP[5]의 경우

DP[4]에서 마지막이 1로 끝나는 애들을 제거해주면된다고 생각했다.

121 1 (X)
31 1   (X)
13 1   (O)

 

그래서 DP[4] - DP[3]으로 생각했지만

DP[3]에서 2, 1은 뒤에 1이 올 수 없기 때문에 진작에 DP[4]에서 사라졌다.

따라서, 정확한 값을 도출 할 수없다.

( DP[4]-DP[3] = 3-3 = 0 )

2차 시도

그래서 끝에 오는 수 (1,2,3) 을 각각 배열에 저장해서 이차원배열로 접근하면 좋을 것 같다고 생각했다.

 

만약 DP[5][1]은 DP[4][2] + DP[4][3] 이다. 왜냐하면 DP[4][1]은 1로 끝나기 때문에 1이 또 올 수 없다.

마찬가지로 DP[5][2]의 경우, DP[3][1] + DP[3][3] 으로 도출 할 수 있다.

DP[5][3] = DP[2][1] + DP[2][2]

 

따라서, 점화식은 다음과 같다.

dp[i][1] = (dp[i - 1][2] + dp[i - 1][3])% 1000000009;
dp[i][2] = (dp[i - 2][1] + dp[i - 2][3])% 1000000009;
dp[i][3] = (dp[i - 3][1] + dp[i - 3][2])% 1000000009;

나머지 수를 구하는 것에 유의하자!

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#define MAX 100001

using namespace std;

int n, m;

long long dp[MAX][4];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;

	dp[1][1] = 1;
	
	dp[2][2] = 1;

	dp[3][1] = 1;
	dp[3][2] = 1;
	dp[3][3] = 1;

	dp[4][1] = 2;
	dp[4][3] = 1;

	for (int i = 5; i <= 100000; i++) {
		dp[i][1] = (dp[i - 1][2] + dp[i - 1][3])% 1000000009;
		dp[i][2] = (dp[i - 2][1] + dp[i - 2][3])% 1000000009;
		dp[i][3] = (dp[i - 3][1] + dp[i - 3][2])% 1000000009;

	}

	int tmp;
	for (int i = 1; i <= n; i++) {
		cin >> tmp;
		cout << (dp[tmp][1] + dp[tmp][2] + dp[tmp][3]) % 1000000009 << '\n';

	}
	
}