BOJ - 2309. 일곱 난쟁이

문제

9개의 배열값이 주어짐. 그중 7개의 합이 100이 되는 요소를 정렬해서 출력하라.
https://www.acmicpc.net/problem/2309

• 입력

20
7
23
19
10
15
25
8
13

• 출력

7
8
10
13
19
20
23

해결 O(N^2)

2개를 선택하는 모든 경우의수 (2개를 제외하고 모두 더했을때 100이 나오는지 체크)

#include <iostream>
#include <algorithm>
#define NSIZE 9

int main(void)
{
        int arr[NSIZE];
        int ret[NSIZE - 2];
        bool found = false;
        int sum = 0;
        int retcnt = 0;

        for (int i = 0; i < NSIZE; i++)
                std::cin >> arr[i];

        for (int i = 0; i < NSIZE; i++) {
                for (int j = i + 1; j < NSIZE; j++) {
                        sum = 0;
                        retcnt = 0;
                        for (int k = 0; k < NSIZE; k++) {
                                if (k == i || k == j)
                                        continue;
                                sum += arr[k];
                                ret[retcnt++] = arr[k];
                        }
                        if (sum == 100) {
                                found = true;
                                break;
                        }
                }
                if (found)
                        break;
        }

        std::sort(ret, ret + NSIZE - 2);
        for (int i = 0; i < NSIZE - 2; i++)
                std::cout << ret[i] << std::endl;
        return 0;
}

해결 O(?)

std::next_permutation() 함수 사용. 9개 값의 모든 경우의 수를 나열하고 그중 앞 7개까지만 합이 100이 맞는지 체크.

• std::next_permutation() 함수
  • 순열(서로다른 n개의 원소를 나열하는 모든 경우의수)을 구하는 함수
    https://cplusplus.com/reference/algorithm/next_permutation/
  • 가령 {1, 2, 3}의 원소들의 모든 순열은 다음과 같음
    {1, 2, 3}
    {1, 3, 2}
    {2, 1, 3}
    {2, 3, 1}
    {3, 1, 2}
    {3, 2, 1}
  • std::next_permutation() 사용전에 컨테이너가 사전에 오름차순 정렬되어있어야함.
  • 중복된 값이 있다면 중복을 제외하고 순열을 리턴함.
  • 사용방법은 do { ... } while (std::next_permutation(arr, arr + 9)) 로 사용.
    그러면 arr배열은 매 반복 때마다 순서가 바뀌게 됨.

#include <iostream>
#include <algorithm>
#define NSIZE 9

void solution2()
{
	int arr[NSIZE];
	int sum = 0;

	for (int i = 0; i < NSIZE; i++)
		std::cin >> arr[i];
	std::sort(arr, arr + NSIZE);

	do {
		sum = 0;
		for (int i = 0; i < NSIZE - 2; i++) sum += arr[i];
		if (sum == 100) break;
	} while (std::next_permutation(arr, arr + NSIZE));

	for (int i = 0; i < NSIZE - 2; i++)
		std::cout << arr[i] << std::endl;
}

int main(void)
{
	//solution1(); // O(N^2)
	solution2(); // using next_permutation
	return 0;
}