백준 15990번 1, 2, 3, 더하기 5

www.acmicpc.net/problem/15990

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

예제 입력 1 복사

3 4 7 10

예제 출력 1 복사

3 9 27

#include <iostream>
using namespace std;

int cnt;

void dfs(int n, int sum, int prev)
{
	if (sum == n)
	{
		cnt++;
	}
	if (sum > n)
		return;
	for (int i = 1; i <= 3; i++)
	{
		if (prev != i)
			dfs(n, sum + i, i);
	}
}

int main(void)
{
	int n, t;
	cin >> t;
	for (int i = 0;i < t; i++)
	{
		cin >> n;
		cnt = 0;
		dfs(n, 0, 0);
		cout << cnt % 1000000009 << "\n";
	}
}

dfs로 푼 문제 

시간초과 당해서 다른 코드 참고해서 고침 

#include <iostream>
using namespace std;
long long dp[100001][4];
int main() {
	int T, temp;
	cin >> T;
	dp[1][1] = 1; dp[2][2] = 1;
	dp[3][1] = 1; dp[3][2] = 1; dp[3][3] = 1;
	for (int i = 4; 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;
	}
	for (int i = 0; i < T; i++) {
		cin >> temp;
		cout << (dp[temp][1] + dp[temp][2] + dp[temp][3]) % 1000000009 << endl;
	}
}

더하면 int 범위를 벗어날 수 있기 때문에 long long 을 꼭 써야 한다.