[BOJ / DP] 15990 1,2,3 더하기 5

www.acmicpc.net/problem/15990

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

 

15990 1,2,3 더하기 5

 

알고리즘 : DP

1차원 배열 DP로 시도하다가 점화식에 문제가 있다는 걸 발견하고 3차원 배열 DP로 바꾸었습니다.

같은 수를 두번 이상 연속해서 사용하면 안되므로 1차원 배열 DP에서 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 에서

dp[i-1]에서 +1로 끝나는 dp[i-2]를 빼고 dp[i-2]에서 dp[i-4]를 빼고 dp[i-3]에서 dp[i-6]을 빼려다

빼는 부분에서도 다시 빼야하는 경우가 있어 3차원 배열 DP로 바꿔

dp[i][j] = i를 나타낼 수 있는 j(<= 3)으로 수식이 끝나는 것의 개수

즉, dp[i][0] = dp[i][1] + dp[i][2] + dp[i][3]

   -   dp[i][1] = i를 만들 수 있는 +1로 끝나는 수식

   -   dp[i][2] = i를 만들 수 있는 +2로 끝나는 수식

   -   dp[i][3] = i를 만들 수 있는 +3로 끝나는 수식

 

모듈러 처리는 (A + B + C) % MOD = ((A + B) % MOD + C) % MOD 입니다.

 

 

 

 

 

 

 

< CODE >

#include <iostream>
#include <algorithm>
#include <climits>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <string.h>
#include <cstdlib>

using namespace std;

#define MAX 100005
#define MOD 1000000009

typedef long long int ll;

ll dp[4][MAX];

void baseQuery(ll num, ll remain, int last)
{
	if(remain == 0)
	{
		dp[0][num]++;		
		dp[last][num]++;
	}
	
	for(int i = 1; i <= 3; i++)
	{
		if(i != last && remain >= i)
			baseQuery(num, remain - i, i);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int tests;
	
	cin >> tests;
	
	for(int i = 1; i <= 7; i++)
		baseQuery(i, i, -1);
	
	for(int i = 8; i <= 100000; i++)
	{
		dp[1][i] = (dp[2][i - 1] + dp[3][i - 1]) % MOD;
		dp[2][i] = (dp[1][i - 2] + dp[3][i - 2]) % MOD;
		dp[3][i] = (dp[1][i - 3] + dp[2][i - 3]) % MOD;
		
		dp[0][i] = (dp[1][i] + dp[2][i] + dp[3][i]) % MOD;
	}

	while(tests--)
	{
		int n;
		
		cin >> n;
		
		cout << dp[0][n] << '\n';
	}
	
	return 0;
}

시간 : 4ms

 

태그 : #BOJ 15990 #BOJ 1,2,3더하기 #BOJ  1,2,3더하기 5 #1,2,3더하기 5 #DP