[C/C++] 백준 14651번 - 걷다보니 신천역 삼 (Large) (DP)

 

<코드>

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

long long n, ans;
long long dp[33334][3];

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

	cin >> n;
	
	dp[1][0] = 0;
	dp[1][1] = 1;
	dp[1][2] = 1;

	for (int i = 2; i <= n; i++)
	{
		dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 1000000009;
		dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 1000000009;
		dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 1000000009;
	}

	cout << dp[n][0];
}

 

풀이 방법

 

dp[i][j] = 0,1,2로 만들 수 있는 i자리수들 중에서 각 자리수들을 더하고 3으로 나눴을 때 j가 되는 수들의 개수

 

www.acmicpc.net/problem/14651

14651번: 걷다보니 신천역 삼 (Large)