[C++] 1, 2, 3 더하기 (9095번)

1, 2, 3 더하기

문제

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

입력

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

출력

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

---

문제풀이

전형적인 dp 문제이다.

처음부터 하나씩 생각해 보자.

1일 경우, 1 하나 이므로 나타내는 방법은 1가지 이다.

2일 경우, 1+1, 2 이므로 나타내는 방법은 2가지 이다.

3일 경우 1+1+1, 1+2, 2+1, 3 이므로 나타내는 방법은 4가지 이다.

4일경우 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 3+1, 1+3 이므로 나타내는 방법은 7가지 이다.

 

4일 경우를 한번 봐보면, 3일 경우에 1을 더한 4개, 2일경우에 2를 더한 2개, 1일경우에 3을 더한 1개로 7개인것을 확인할 수 있다.

 

즉 아주 간단한 점화식인  n>4; arr[n] = arr[n-1] + arr[n-2] + arr[n-3] 가 성립한다.

4를 만드는 방법이, 3일때 1을 더하는 것과, 2일때 2를 더하는 것과, 1일때 3을 더하는 방법을 합치면 구할 수 있다.

이 문제가 조금 꼬아본다면, 1 2 1, 1 1 2, 2 1 1 을 하나로 보는 경우도 생각해보면 좋을것 같다.

 

#include <iostream>

using namespace std;

int main() {
	int n;
	cin >> n;
	int arr[12];
	arr[0] = 0;
	arr[1] = 1;
	arr[2] = 2;
	arr[3] = 4;
	for(int i=4; i<=11; i++)
		arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
	
	for(int i=0; i<n; i++) {
		int k;
		cin >> k;
		cout << arr[k] << "\n";
	}
	
	return 0;
}

 11까지 미리 값을 구해두고, 답을 출력하게 하였다.