[백준 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의 합으로 나타내는 방법의 수를 출력한다.

---

C++ 풀이

#include <iostream>
#include <string>
using namespace std;

int c;
void func(int number) {
	if (number == 1)
		c++;
	else if (number == 2)
		c += 2;
	else if (number == 3)
		c += 4;
	else if (number == 4)
		c += 7;
	else {
		func(number - 3);
		func(number - 2);
		func(number - 1);
	}
}

int main() {
	int T, n;
	cin >> T;
	for (int i = 0; i < T; i++) {
		c = 0;
		cin >> n;
		func(n);
		cout << c << endl;
	}
}

이미 알고 있는 정보 활용

1은 한가지 방법

2는 (1+1, 2) 두가지 방법

3은 (1+1+1, 1+2, 2+1, 3) 네가지 방법

4는 문제 예시와 같이 일곱가지 방법으로 나타낼 수 있다.

 

1, 2, 3, 4는 이미 방법의 수를 알고 있기 때문에 1, 2, 3, 4만 남도록 계속해서 1 or 2 or 3을 빼준 후 func 함수를 실행한다.

 

11보다 작은 수를 문제로 주었기 때문에 가능한 풀이인 것 같다. 더 큰 수가 문제로 주어질 경우, 이미 방법의 수를 구한 수에서 1 or 2 or 3을 더해서 푸는 방식이 필요할 것이다.

 

문제 링크

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

9095번: 1, 2, 3 더하기