[Baekjoon] 15663번: N과 M (9)

🥅 문제

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

 

🔍 설계

처음에는 백트래킹을 사용하여 사전 순으로 모든 경우를 구한 후, 중복을 제거하는 방식을 사용했으나, 문제 의도에 맞지 않는 것 같아 다른 방법을 고민했다.

 

이 문제에서의 핵심은 답을 구성하는 수열에서 같은 인덱스에서는 중복된 수가 오면 안되고, 다른 인덱스에서는 중복이 가능하다. 따라서, 같은 인덱스에서 중복을 방지하도록 그 인덱스에서 마지막에 사용한 수를 저장하여 다른지 확인해야 한다.

 

👊 풀이1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<int> number(8);
vector<bool> visited(8);
vector<int> temp;
vector<vector<int>> result;

void bt(int count) {
	if (count == m) {
		result.push_back(temp);
	}
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			visited[i] = true;
			temp.push_back(number[i]);
			bt(count + 1);
			temp.pop_back();
			visited[i] = false;
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> number[i];
	}
	sort(number.begin(), number.begin() + n);
	
	bt(0);

	sort(result.begin(), result.end());
	result.erase(unique(result.begin(), result.end()), result.end());
	for (int i = 0; i < result.size(); i++) {
		for (int j = 0; j < m; j++) {
			cout << result[i][j] << " ";
		}
		cout << "\n";
	}
	
	return 0;
}

 

👊 풀이2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<int> number(8);
vector<bool> visited(8);
vector<int> temp;

void bt(int count) {
	if (count == m) {
		for (int i = 0; i < m; i++) {
			cout << temp[i] << " ";
		}
		cout << "\n";
	}
	int same_level_last = 0;
	for (int i = 0; i < n; i++) {
		if (!visited[i] && same_level_last != number[i]) {
			same_level_last = number[i];
			visited[i] = true;
			temp.push_back(number[i]);
			bt(count + 1);
			temp.pop_back();
			visited[i] = false;
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> number[i];
	}
	sort(number.begin(), number.begin() + n);
	
	bt(0);
	
	return 0;
}

 

📖 레퍼런스

 

📝 메모