백준 문제풀이 - 2309 번

링크 -> https://www.acmicpc.net/problem/2309

1. 요약 및 풀이방법

집으로 들어온 아홉 난쟁이 중, 진짜 일곱 난쟁이를 찾는 문제이다.
진짜 일곱난쟁이의 키의 합은 100이므로
9C7 의 모든 키 조합에서 키의 합이 100이 되는 경우를 찾는다.

조합(Combination) 알고리즘을 사용하여 문제를 해결했다.

Combination 알고리즘 해결 도움받은 링크

2. Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

typedef std::vector<int> Intvct;

void input(Intvct &data)
{
	int tmp;

	for (int i = 0; i < 9; i++) {
		std::cin >> tmp;
		data[i] = tmp;
	}
}

void combination(Intvct data, Intvct selected, int n,  int r, int index, int depth)
{
	if (r == 0)	// 9C7 조합 중 한 경우.
	{
		if (std::accumulate(selected.begin(), selected.end(), 0) == 100)	// 우리가 찾는 조건.
		{
			for (int i = 0; i < 7; i++)
			{
				std::cout << selected[i] << std::endl;
			}
			exit(0);
		}
	}
	else if (n == depth)
		return ;
	else
	{
		selected[index] = data[depth];
        	//data[depth] 원소를 선택한 경우.
		combination(data, selected, n, r - 1, index + 1, depth + 1);
        	//data[depth] 원소를 선택하지 않은 경우. (아래의 재귀 함수 안에서 selected[index]에 값을 대입하기 때문에, 선택하지 않은것으로 생각한다.
		combination(data, selected, n, r, index, depth + 1);
	}
}

int main()
{
	int n = 9, r = 7;
	Intvct data(n);
	Intvct selected(r);

	input(data);

	std::sort(data.begin(), data.end());

	combination(data, selected, n, r, 0, 0);

	return (0);
}

3. 학습 내용

문제를 보고 예전에 수학에서 배웠던 순열조합이 바로 생각나긴 했으나, 코드로 조합을 직접 구현해본적은 없었다.
덕분에 직접 재귀함수 형태를 사용하여 처음으로 조합 알고리즘을 구현해보는 경험이 됨.
브루트포스 알고리즘 문제들에서 종종 필요할 것으로 예상되기 때문에, 좋은 경험이 된 것 같다.

4. 결과