[백준] 1469. 숌 사이 수열(c++)

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

 

백트래킹 문제이다.

조건이 조금 까다롭다.

visited 배열은 해쉬방식으로 선언했다. 또한 arr배열(입력배열)은 -1로 설정해서 0을 놓치지 않도록 하는게 중요하다.

백트래킹... 반드시 잘해야지

---

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <cstring>
using namespace std;

using ll = long long;

vector<int> arr;
int ans[30];
int visited[30];

int n;

void dfs(int idx) {
	if (idx == 2 * n) {
		for (int i = 0; i < 2 * n; i++) {
			cout << ans[i] << " ";
		}
		exit(0);
	}

	if (ans[idx] != -1) {
		dfs(idx + 1);
		return;
	}

	for (int i = 0; i < n; i++) {
		if (!visited[arr[i]] && idx + arr[i] +1 < n * 2 && ans[idx] == -1 && ans[idx + arr[i] +1] == -1) {
			visited[arr[i]] = 1;
			ans[idx] = ans[idx + arr[i] + 1] = arr[i];
			dfs(idx + 1);
			ans[idx] = ans[idx + arr[i] + 1] = -1;
			visited[arr[i]] = 0;
		}
	}
}

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

	cin >> n;



	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		arr.push_back(temp);
	}
	
	sort(arr.begin(), arr.end());
	memset(ans, -1, sizeof(ans));
	
	dfs(0);

	cout << -1;

	return 0;
}