[백준 2309] 일곱 난쟁이 (C++/Python)

C++) 백트래킹 - 합이 100이 되는 경우 찾기

#include <iostream>
#include <algorithm>
#define MAX_NUM 10
using namespace std;

bool isFind;
int ans[7];
int arr[MAX_NUM];
bool visited[MAX_NUM];

void func(int cnt, int cur, int sum) {
	if (isFind)
		return;

	if (cnt == 7) {
		if (sum == 100) {
			sort(ans, ans + 7);
			for (int i = 0; i < 7; i++)
				cout << ans[i] << "\n";
			isFind = true;
		}
		return;
	}

	for (int i = cur; i < 9; i++) {
		if (!visited[i]) {
			visited[i] = true;
			ans[cnt] = arr[i];
			func(cnt + 1, i + 1, sum + arr[i]);
			visited[i] = false;
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	for (int i = 0; i < 9; i++)
		cin >> arr[i];
	
	func(0,0,0);

	return 0;
}

 

 

 

Python) 완전탐색 - 난쟁이 두 명의 합을 뺀 숫자가 100인 경우 찾기

import sys

arr = [0] * 9
sum = 0

for i in range(9):
    arr[i] = int(sys.stdin.readline().rstrip())
    sum += arr[i]
    
isFind = False
for i in range(9):
    if isFind:
        break

    for j in range(i+1, 9):
        if sum - (arr[i] + arr[j]) == 100:
            arr.pop(j)
            arr.pop(i)

            isFind = True

            break

arr.sort()
print('\n'.join(map(str, arr)))

 

100이 되는 경우가 여러개인데 시간 더 쓰기 싫어서 isFind로 탈출하게 해줬다.