백준 15663 - N과 M(9)(C++)

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

15663번: N과 M (9)

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

N개의 수가 주어졌을 때 M개의 수를 선택하고 출력하는 문제입니다.

N개의 수가 중복되어 주어질 수도 있으며, 선택된 수열이 항상 오름 or 내림차순이 아닐 수도 있는 것이 다른 점이였습니다.

 

저는 중복된 수가 들어왔을 때, 중복된 수를 모두 없애줬습니다. -> 백터를 사용하면 편합니다.

예를 들어 (9 7 9 1)이 입력되었을 때, (1 7 9)로 만들어 줬습니다.

하지만 9가 2번이 들어왔기에, 9를 2번 출력해야합니다. 

따라서 check 배열을 만들어, X번째 수가 몇번이 들어왔는지를 확인했습니다.

 

 

1. 중복된 수 없애기

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

vector로 선언된 num이 있을 때, N개의 수를 num에 저장했습니다.

vector의 경우, 중복된 수를 erase + unique를 통해 없앨 수 있는데, 이때 정렬을 해준 상태에서 해야합니다.

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

 

 

 

2. M개 만큼 수 출력하기

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++) {
			if (check[num[i]] > 0) {
				number.push_back(num[i]);
				check[num[i]]--;
				select_number(0, cnt + 1);
				number.pop_back();
				check[num[i]]++;
			}
		}
	}
}

선택된 M개의 수가 항상 오름차순이거나 내림차순이 아닙니다. 따라서 수를 하나 선택했다면, 처음부터 다시 시작해 선택하는 것이 중요했습니다.

 

방금 중복된 수를 없앴기 때문에, num만을 사용한다면 같은 수를 2번 이상 출력할 수 없습니다.

따라서 check 배열에 X가 몇번 나왔는지를 저장했습니다.

따라서 X를 선택할 때마다 check[X]의 값을 1씩 줄여 X가 선택되었음을 나태냈습니다.

 

수를 선택할 조건은 check[X]가 0보다 클 경우(아직 선택할 수 있다는 의미)에 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;
int check[10001];
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++) {
			if (check[num[i]] > 0) {
				number.push_back(num[i]);
				check[num[i]]--;
				select_number(0, cnt + 1);
				number.pop_back();
				check[num[i]]++;
			}
		}
	}
}

void solve() {
	num.erase(unique(num.begin(), num.end()), num.end());
	for (int i = 0; i < num.size(); i++) {
		number.push_back(num[i]);
		check[num[i]]--;
		select_number(0, 1);
		check[num[i]]++;
		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;
		check[x]++;
		num.push_back(x);
	}
	sort(num.begin(), num.end());
	solve();
	return 0;
}

 

 

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