N과 M 시리즈를 전부 따로 포스팅 하면 너무 많아서 비슷한 유형을 모았다
#include <iostream>
#include <algorithm>
#define MAX 9
using namespace std;
int n, m;
bool visited[MAX];
int arr[MAX];
int ans[MAX];
void dfs(int depth) {
if (depth == m) {
for (int i = 0; i < m; i++) {
cout << ans[i] << " ";
}
cout << '\n';
return;
}
for (int i = 0; i < n; i++) {
if (!visited[i]) {
visited[i] = true;
ans[depth] = arr[i];
dfs(depth + 1);
visited[i] = false;
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
sort(arr, arr + n);
dfs(0);
return 0;
}
이번에는 입력 값이 주어지는 수로 수열을 구하는 문제이다
배열에 모든 값을 입력 받고, 정렬을 해주는 과정만 더하면 N과 M(1)
과 동일한 문제임을 알 수 있다!
중복을 허용하지 않는 수열이므로 visited
방문 체크를 해주고 ans
라는 임의 배열에 담아주면 끝
#include <iostream>
#include <algorithm>
#define MAX 9
using namespace std;
int n, m;
bool visited[MAX];
int arr[MAX];
int ans[MAX];
void dfs(int index, int depth) {
if (depth == m) {
for (int i = 0; i < m; i++) {
cout << ans[i] << " ";
}
cout << '\n';
return;
}
for (int i = index; i < n; i++) {
if (!visited[i]) {
visited[i] = true;
ans[depth] = arr[i];
dfs(i + 1, depth + 1);
visited[i] = false;
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
sort(arr, arr + n);
dfs(0, 0);
return 0;
}
마찬가지로 입력 받은 값을 정렬해 준 후에 오름차순으로 출력하는 N과 M (2)
같은 문제이다
중복을 허용하지 않으니 visited
를 사용해서 방문을 체크해준다.
#include <iostream>
#include <algorithm>
#define MAX 8
using namespace std;
int n, m;
int arr[MAX];
int ans[MAX];
void dfs(int depth) {
if (depth == m) {
for (int i = 0; i < m; i++) {
cout << ans[i] << " ";
}
cout << '\n';
return;
}
for (int i = 0; i < n; i++) {
ans[depth] = arr[i];
dfs(depth + 1);
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
sort(arr, arr + n);
dfs(0);
return 0;
}
값을 입력 받아 중복 순열을 추출하는 문제이다
N과 M(3)
문제와 동일하다고 볼 수 있다.
마찬가지로 입력 값을 정렬한 뒤에 ans에 출력할 값을 저장하여 출력한다
입력 받는 부분 생략
void dfs(int index, int depth) {
if (depth == m) {
for (int i = 0; i < m; i++) {
cout << ans[i] << " ";
}
cout << '\n';
return;
}
for (int i = index; i < n; i++) {
ans[depth] = arr[i];
dfs(i, depth + 1);
}
}
입력 값을 위의 문제와 동일하다.
중복 순열에 비내림차순이 조건이므로 dfs
파라미터로 i
를 넘기고, visited
방문 체크를 하지 않음으로서 문제를 해결할 수 있다.
여기까지 서로 다른 자연수의 입력값이 주어질 때 순열 조합을 출력하는 문제였다.