[BOJ] 백준 15656번 N과 M (7)

링크

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

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

N개의 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

 // 백트래킹.. nPr 인데 같은 원소의 중복이 가능하다. -> next_permutation은 사용 불가.
// N개의 자연수를 넣을 num배열이 필요하고, arr배열이 필요하고 
// 같은 원소의 중복 ->  모두 방문해야하므로 vis배열이 필요없다.

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

int n, m;
int arr[10];
int num[10];

void solve(int cur) {
	if (cur == m) { //cur는 현재 arr에 원소 들어간 갯수 
		for (int i = 0; i < m; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = 0; i < n; i++) {
			arr[cur] = num[i]; //arr배열의 cur인덱스에 num원소를 차례대로 넣는다.
			solve(cur + 1);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}
	sort(num, num + n); //정렬
	solve(0);
	
}

설명

백트래킹.. nPr 인데 같은 수를 여러번 골라도 된다.-> next_permutation은 사용 불가.
N개의 자연수를 넣을 num배열이 필요하고, arr배열이 필요하고
같은 원소의 중복 -> 모두 방문해야하므로 vis배열이 필요없다.