[C 언어] 백준 #9095 - 1, 2, 3 더하기

 

문제

---

9095번을 숫자 하나를 입력하면 순서를 고려하지 않은 더하기 경우의 수를 출력하도록 변형했다.

 

입력

• 4

 

출력

• 5

경우의 수 >>

1 + 1 + 1 + 1

1 + 1 + 2

1 + 3

2 + 2

4

 

입력	출력
4	5

 

풀이

---

풀이 핵심

 

>> 조합 사용

1) bucket 정보

    n개의 공간 동적으로 할당

 

2) 경우의 수를 셀 전역 변수 사용

    pick 함수 내에서 변수를 선언한다면 재귀 호출이 되었을 때 0으로 돌아가기 때문에 전역변수로 받았다. 물론 함수 매개변수로 받아도 문제는 없다. 

// 1, 2, 3 더하기 쉽게 변형
// 중복 조합
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>

int result = 0;

void pick(int n, int* bucket, int m, int k)
{
	int i, lastIndex, smallest;
	int total = 0;

	lastIndex = m - k - 1;

	for (i = 0; i <= lastIndex; i++)
		total += bucket[i] + 1;

	if (total == n) { // 다 뽑았으면
		result++;
		return;
	}
	else if (total > n)
		return;

	if (m == k)
		smallest = 0;
	else
		smallest = bucket[lastIndex];

	for (i = smallest; i < n; i++) {
		bucket[lastIndex + 1] = i;
		pick(n, bucket, m, k - 1);
	}
}

int main(void)
{
	int n;
	int* bucket;

	scanf("%d", &n);
	bucket = (int*)malloc(sizeof(int) * n);

	pick(n, bucket, n, n);
	printf("%d\n", result);

	return 0;
}