[BOJ] 23057번_도전 숫자왕_백트래킹 (C++)

[문제]

https://www.acmicpc.net/problem/23057

N개의 카드가 주어졌을 때 모든 카드에 쓰여있는 숫자의 합을 M이라고 하자. 이때 1 이상 M 이하의 자연수 중 만들 수 없는 수의 개수를 출력하는 문제이다.

[사용 알고리즘]

백트래킹

[풀이 핵심]

• Solve함수에서 원소를 탐색해가며 나오는 값들을 set에 넣어준다. 카드에 써있는 값의 합이 중복이 되면 안되므로 set을 이용해서 풀면 좋다.
• 전체 합에서 나올 수 있는 수의 개수를 빼주면 나올 수 없는 수의 개수이므로 M - set의 크기(sum.size())가 정답이다.

[코드]

//boj23057번_도전 숫자왕_백트래킹

#include<iostream>
#include<set>

using namespace std;

int N;
int arr[21];
set<int> sum;

void Solve(int count, int card) {
	sum.insert(card);

	if (count == N) {
		return;
	}

	Solve(count + 1, card + arr[count + 1]);
	Solve(count + 1, card);
}

int main() {
	cin >> N;

	int M = 0;

	for (int i = 0; i < N; i++) {
		cin >> arr[i];

		M += arr[i];
	}

	for (int i = 0; i < N; i++) {
		Solve(i, arr[i]);
	}

	cout << M - sum.size();

	return 0;
}