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

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

문제 요약

정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

문제 풀이

1. 계산할 숫자의 수를 입력받습니다. 그 수만큼 반복문을 만들어 계산할 숫자를 입력받습니다. ( n은 0보다 크고 11보다 작아야 합니다.)

2. bottom-up을 해줄 함수 dp를 만듭니다. 이 함수에서는 1부터 11까지의 1, 2, 3의 합으로 나타내는 방법의 수를 배열에 담아줍니다.

3. 1부터 3까지 패턴이 없는 수 까지는 초기값을 주고, 4부터는 1전항 2전항 3전항의 총합을 저장해주도록 짭니다.

4. 계산할 수들을 만든 배열의 인덱스에 넣고 출력합니다.

주의할 점

이 문제는 다이나믹 프로그래밍 알고리즘인 bottom-up 알고리즘을 이용하여 풀어야하는 문제입니다.

패턴이 4부터 생기기 때문에 3까지 초기값을 주어 4부터 계산해야 합니다.

코드

#include<iostream>
#include<vector>

using namespace std;

vector<int>v;

int p[11];
int n;
int t;

void dp()
{
	// 최대값인 11까지의 1, 2, 3의 합으로 나타내는 방법의 수 저장
	p[1] = 1;
	p[2] = 2;	
	p[3] = 4;
	for (int i = 4; i <= 11; i++)
	{
		p[i] = p[i - 1] + p[i - 2] + p[i - 3];
	}
}

int main()
{
	cin >> t;

	for (int i = 0; i < t; i++)
	{
		cin >> n;
		if (n <= 0 || n > 10)
		{
			return 0;
		}
			v.push_back(n);
	}

	dp();

	// 입력 받은 값들 출력
	for (int i = 0; i < t; i++)
	{
		cout << p[v[i]] << "\n";
	}

	return 0;

}

반응형

예제

3
4
7
10

결과