15990 1,2,3 더하기 5

https://www.acmicpc.net/problem/15990

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

1, 2, 3 더하기 5 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

4074

1506

1033

34.376%

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

• 1+2+1
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

 

<풀이>

1. 문제의 조건식에 같은 수를 연속으로 사용하면 안되는 조건이 있음.

 

2. 연속 사용하면 안되는 수를 파악하기위해 기존 1,2,3 더하기 점화식을 변경할 필요가 있다.

 

3. D[N][K] = > 1,2,3 의 합으로 N을 만드는데 끝자리가 K인 수

 

4. D[N][1] = D[N-1][2] + D[N-1][3]  -> 끝자리가 1이므로  2 와 3이 와야한다

 

5. 위와 같이 1,2,3 을 식을 세워주면 모든 경우의 수를 구할 수 있다.

 

6. 나머지 구현

 

#include<iostream>
using namespace std;

unsigned long long d[100001][4];


const long long val = 1000000009LL;
unsigned long long go(int n, int i);
int main(void)
{
	for (int i = 1; i <= 100000; ++i)
	{
		if (i - 1 >= 0)
		{
			d[i][1] = d[i - 1][2] + d[i - 1][3];
			if (i == 1)
				d[i][1] = 1;
		}
		if (i - 2 >= 0)
		{
			d[i][2] = d[i-2][1] + d[i-2][3];
			if (i == 2)
				d[i][2] = 1;
		}
		if (i - 3 >= 0)
		{
			d[i][3] = d[i-3][1] + d[i-3][2];
			if (i == 3)
				d[i][3] = 1;
		}
		d[i][1] %= val;
		d[i][2] %= val;
		d[i][3] %= val;
	}

	int N;
	cin >> N;
	while (N--)
	{
		int n;
		cin >> n;
		int ans = (d[n][1] + d[n][2] + d[n][3]) % val;
		cout << ans << '\n';
	}

	return 0;
}
/*
unsigned long long go(int n, int i)
{
	if (n < 0) return 0;
	if (n == i) return 1;
	if (d[n][i]) return d[n][i];
	if (i == 1) {
		d[n][i] = go(n - 1, 2) + go(n - 1, 3);
		d[n][i] %= val;
	}
	else if (i == 2) {
		d[n][i] = go(n - 2, 1) + go(n - 2, 3);
		d[n][i] %= val;
	}
	else if (i == 3) {
		d[n][i] = go(n - 3, 1) + go(n - 3, 2);
		d[n][i] %= val;
	}
	return d[n][i];

}*/