백준 15666 - N과 M(12)(C++)

문제 링크입니다. https://www.acmicpc.net/problem/15666

15666번: N과 M (12)

vector와 백트래킹을 이용한 문제입니다.

M개가 선택된 수가 항상 오름차순이여야 되며, 같은 수가 여러번 선택되도 됩니다.

N개가 입력될 때, 중복된 수가 입력될 수 있기에, 저는 중복된 수를 지우고 시작했습니다. 

 

1. 중복된 수 지우기

	sort(num.begin(), num.end());
	num.erase(unique(num.begin(), num.end()), num.end());

vector을 이용하면 중복된 수를 쉽게 지울 수 있습니다.

erase + unique를 이용하면 지울 수 있는데, 이때 정렬이 된 상태여야 가능합니다.

따라서 정렬을 먼저한 뒤, 중복된 수를 지웠습니다.

 

 

X번째 수가 여러번 선택될 수 있으니, check 배열을 통해 X번째 수의 선택 여부를 저장하는 방법으로 하면 안됩니다.

바로 백트래킹을 하게 해줍니다.

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>

using namespace std;

int N, M;
vector<int> num;
vector<int> number;

void select_number(int x, int cnt) {
	if (cnt == M) {
		for (int i = 0; i < M; i++) {
			cout << number[i] << " ";
		}
		cout << "\n";
	}
	else {
		for (int i = x; i < num.size(); i++) {
			number.push_back(num[i]);
			select_number(i, cnt + 1);
			number.pop_back();
		}
	}
}

void solve() {
	num.erase(unique(num.begin(), num.end()), num.end());
	for (int i = 0; i < num.size(); i++) {
		number.push_back(num[i]);
		select_number(i, 1);
		number.pop_back();
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		num.push_back(x);
	}
	sort(num.begin(), num.end());
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요