[C/C++] 백준 15990번 - 1, 2, 3 더하기 5

 

<코드>

#include<iostream>
#include<algorithm>
using namespace std;
#define MOD 1000000009
int T, n;
long long ans, dp[100001][4];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> T;

	while (T--)
	{
		cin >> n;

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

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

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

		for (int i = 4; i <= n; i++)
		{
			dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % MOD;
			dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % MOD;
			dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % MOD;
		}

		ans = (dp[n][1] + dp[n][2] + dp[n][3]) % MOD;

		cout << ans << '\n';
	}
	
}

 

풀이 방법

 

dp[i][j] : i를 만드는 경우의 수들 중 마지막에 더하는 수가 j인 경우의 수

 

예를들어)

dp[6][1] = 5를 만드는 경우의 수들 중 마지막 더하기가 1로 끝나지않는 경우의 수들 = dp[5][2] + dp[5][3]

dp[6][2] = 4를 만드는 경우의 수들 중 마지막 더하기가 2로 끝나지않는 경우의 수들 = dp[4][1] + dp[4][3]

dp[6][3] = 3을 만드는 경우의 수들 중 마지막 더하기가 3으로 끝나지않는 경우의 수들 = dp[3][1] + dp[3][2]

 

 

www.acmicpc.net/problem/15990

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