백준 15663번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	512MB	실버 2

---

풀이

 며칠만인지 모르겠지만 아무튼 오랜만에 밀린 문제 정리하기다.

 

 이번 N과 M은 원소를 조합으로 뽑는 문제이다. 언제나 그렇듯 사전 기준 오름차순 출력이기 때문에 입력받은 N개의 원소를 정렬한 후, 백트래킹으로 M개의 숫자를 중복없이(같은 인덱스의 원소를 뽑지 않고) 뽑는다. 이때 N개의 원소에는 중복되는 원소가 존재할 수 있다. 이를 모두 고르게 되면 중복되는 수열이 등장하게 된다. 이를 방지하기 위해 map에 출력한 output과 해당 값이 출력되었는지 기록하여, 중복된 수열이 나오더라도 출력은 한번만 되도록 했다.

코드

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
#define endl '\n'
using namespace std;

int n, m;
vector<int> v;
bool check[8];
map<string, bool> answers;

void input() {
	cin >> n >> m;
	v.resize(n);
	for(int& x : v) cin >> x;
	sort(ALL(v));
}

void sol(int cnt, string output) {
	if (cnt == m) {
		if (!answers[output]) {
			cout << output << endl;
			answers[output] = true;
		}
		return;
	}

	for (int i = 0; i < n; i++) {
		if (check[i]) continue;

		check[i] = true;
		sol(cnt + 1, output + to_string(v[i]) + " ");
		check[i] = false;
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	input();
	sol(0, "");
}