☆ [백준/2309번/C++] 일곱 난쟁이

• 문제

 

• 풀이

#include <iostream>
#include <algorithm>

using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int input[9] = { 0 };

	for (int i = 0; i < 9; i++)
	{
		cin >> input[i];
	}

	sort(input, input + 9);

	do
	{
		int sum = 0;
		for (int i = 0; i < 7; i++)
		{
			sum += input[i];
		}

		if (sum == 100)
		{
			break;
		}
	} while (next_permutation(input, input + 9));

	for (int i = 0; i < 7; i++)
	{
		cout << input[i] << '\n';
	}

	return 0;
}

 

• 메모
  문제의 기본 원리는 9개의 수 중에서 7개의 수를 조합해 그 합이 100이 되는 경우 해당값들을 출력하는 것이다.
  DFS 등으로 구하는 방법도 있지만 값을 빠르게 찾기 위해서 순열과 조합을 구할 때 유용한 algrorithm 헤더에 있는 next_permutaion() 함수를 사용했다.
   
  <next_permutaion() 함수>
  이 함수는 값이 들어있는 컨테이너에서 원하는 범위를 입력하면 해당 범위 안의 값을 사전 순의 다음 순열로 바꾼 뒤, 해당 순열이 사전 상의 마지막이라면 true를, 마지막이 아니라면 false를 리턴해준다.
  
  따라서 do-while문과 함께 해당 함수를 사용하면 해당 값을 사용해 만들 수 있는 모든 순열의 경우를 만들 수 있게 된다.
  주의할 점은 모든 경우의 수를 따져보기 위해서는 해당 함수를 사용하기 전에 먼저 sort 함수로 컨테이너의 값을 오름차순으로 정렬해주어야 한다는 점이다.
  이와 비슷하게 내림차순으로 구하는 함수로는 prev_permutation()이 있다.
  
  https://cplusplus.com/reference/algorithm/next_permutation/

https://cplusplus.com/reference/algorithm/next_permutation/