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

문제 - www.acmicpc.net/problem/15990

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

소스코드

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

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

풀이

끝자리 수가 1, 2 , 3 일때 만들 수 있는 경우를 생각해보면 된다.

결국 i - (1, 2 , 3) 을 해주게 되면 중복없이 만들 수 있는 경우의 수들을 저장할 수 있다.

뭔가 좀더 빠른 방법이 있을거 같은데, 여기서 만족하겠다.

머리가 터질거 같으니