[C/C++] 1, 2, 3 더하기 (백준 11726)

문제

 

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

 

입력

 

3
4
7
10

 

출력

 

7
44
274

 

풀이

 

완전 탐색 문제... 라고 생각했습니다. 백트래킹 까지는 아니라고 생각이 들었는데 만약 1+1+2와 2+1+1을 구분하는 문제였다면 조건을 걸어줘야하지만 이건 말그대로 전체적으로 한 번 탐색을 하면 되는 문제라고 생각해서 재귀 함수를 만들어서 풀었습니다.

 

일단 1, 2, 3을 사용해서 푸는 문제이기 때문에 반대로 생각해서 수가 주어지고 그 수를 n이라고 하고 이 n을 이루는 식이 1+1+1+1... 이런식으로 이루어진다면

 

n = 1+1+1+1+1+...

 

이걸 왼쪽 항으로 넘겨주면

 

n-1-1-1-1-1-....= 0

 

이라는 식이 됩니다. 이걸 보고 '아 그냥 재귀로 풀 탐색을 돌리면 되겠구나' 싶었습니다. 그리곤 0이 되면 멈추고 count를 세어주고 혹시나 0보다 작은 숫자가 나온다면 그건 count를 세지 않도록 했습니다.

 

3 = 1+2 이기 때문에 3 -1 -2 = 0 이 성립하지만 3 -2 -2 = -1이 되어 성립하지 않습니다. -2가 2개라면 4가 숫자일 때 성립하는 식이기 때문이죠.

 

이 문제는 처음에 조건만 걸어주면 되는 아주 간단한 문제 였습니다.

 

코드

 

#include <iostream>

int count;

void recursive(int n) {
	if (n == 0) { 
		count++;
		return;
	}
	else if (n < 0) {
		return;
	}
	else{
		recursive(n - 1);
		recursive(n - 2);
		recursive(n - 3);
	}
}

int main(void) {

	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int a;
		scanf("%d", &a);
		recursive(a);
		printf("%d\n", count);
		count = 0;
	}
	
	return 0;
}