C++ / 15988 / 1, 2, 3 더하기 3 ( 다이나믹 프로그래밍 )

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

문제 요약

정수 4를 1, 2, 3의 합으로 나타내느 방법은 총 7가지가 있습니다. 합을 나타낼 때는 수를 1개 이상 사용해야 합니다.

 

- 1 + 1 + 1 + 1

- 1 + 1 + 2

- 1 + 2 + 1

- 2 + 1 + 1

- 2 + 2

- 1 + 3

- 3 + 1

 

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

 

n은 1,000,000보다 작거나 같습니다.

 

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

문제 풀이

1. t를 입력받습니다.

2. n을 long long int로 입력받아 배열에 저장합니다.

3. dp함수를 만들어 정답 배열을 만듭니다. 정답 배열의 사이즈는 1000001이고 long long int형식의 배열입니다.

4. 3까지 초기값을 주고 4부터는 전항 전전항 전전전항의 합을 현재 항에 넣어줍니다. 넣어줄때 % 1000000009하여 조건을 만족시켜 줍니다.

5. 정답배열 인덱스에 입력받은 n을 넣어 출력합니다.

주의할 점

https://lgj415415.tistory.com/53

이 문제는 1, 2, 3 더하기 1과 거의 동일한 코드를 가지고 있습니다.

차이점이 있다면 n의 크기가 더 커졌다는 것, 1000000009로 나눈 나머지를 출력해야 한다는 것 입니다.

long long int형을 선언하고, 1000000009 나머지 연산을 하는 것이 중요합니다.

코드

#include<iostream>
#include<vector>

using namespace std;

long long int p[1000001];
vector<int> v;
long long int n, t;

void dp()
{
	p[0] = 0;
	p[1] = 1;
	p[2] = 2;
	p[3] = 4;
	for (int i = 4; i < 1000001; i++)
	{
		p[i] = (p[i - 1] + p[i-2] + p[i-3])% 1000000009;
	}
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> t;
	for (long long int i = 0; i < t; i++)
	{
		cin >> n;
		v.push_back(n);
	}	
	dp();
	for (long long int i = 0; i < v.size(); i++)
	{
		cout << p[v[i]] << "\n";
	}

	return 0;
}

반응형

예제 

3
4
7
10

결과