[백준/C++] N과 M 시리즈
N과 M 시리즈 12문제
백준에 N과 M이라는 시리즈가 있다. 총 12문제인데 순열조합 문제이다. 부루트포스로 풀어보자
1번
문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
예제 출력 1
1
2
3
예제 입력 2
4 2
예제 출력 2
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3
풀이
결국 모든 순열 NPM을 출력하라는 건데 재귀호출을 통한 완전탐색이 가장 먼저 생각난다. 기저 조건은 M개를 모두 카운트 했을 때 이고, 이 조건에 들어갈 경우 순열을 출력해 준다. subcase는 선택하지 않은 수들 중에서 하나의 수를 선택하는 것이다. 재귀호출이 포함된 코드 앞뒤로 넣었다가 빼는 코드를 추가한다.
이를 구현하면,
#include <iostream>
#include <vector>
using namespace std;
vector<int> v;
bool chosen[9] = {false};
void permutation(int M, int N)
{
if(N == 0) {
for(vector<int>::iterator iter = v.begin(); iter < v.end(); ++iter) {
cout << *iter;
if(iter + 1 != v.end())
cout << ' ';
}
cout << endl;
return;
}
for(int i = 1; i < M + 1; ++i) {
if(!chosen[i]) {
chosen[i] = true;
v.push_back(i);
permutation(M, N - 1);
chosen[i] = false;
v.pop_back();
}
}
return;
}
int main()
{
int M, N;
cin >> M >> N;
permutation(M, N);
return 0;
}
2번
문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
예제 출력 1
1
2
3
예제 입력 2
4 2
예제 출력 2
1 2
1 3
1 4
2 3
2 4
3 4
풀이
요컨데 앞의 문제와의 유일한 차이점은 첫 번째 수보다 작은 수가 그 뒤에 나와서는 안된다는 점이다. algospot의 튜토리얼과 종만북에서 재귀호출 문제들을 풀면서 배운 아주 효과적인 방법은 index를 제한하는 것인 이 경우 main으로 돌아가는 for 루프문 전에 index를 설정하는 for 루프문을 추가하는 것이 좋아보인다. index의 최대값부터 1씩 감소하면서 처음으로 true값을 만나는 지점을 찾아 index로 설정하여 다음 for 루프로 넘겨준다. 그 외에는 첫 번째 문제와 같다.
#include <iostream>
#include <vector>
using namespace std;
vector<int> v;
bool chosen[9] = {false};
void combination(int N, int M)
{
if(M == 0) {
for(vector<int>::iterator iter = v.begin(); iter < v.end(); ++iter)
cout << *iter << ' ';
cout << "\n";
return;
}
int index;
for(index = 8; index > 0; --index) {
if(chosen[index]) break;
}
for(int i = index + 1; i < N + 1; ++i) {
chosen[i] = true;
v.push_back(i);
combination(N, M - 1);
chosen[i] = false;
v.pop_back();
}
return;
}
int main()
{
int N, M;
cin >> N >> M;
combination(N, M);
return 0;
}
3번
문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)
출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
예제 출력 1
1
2
3
예제 입력 2
4 2
예제 출력 2
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4
풀이
1번과의 차이점은, 자기자신을 포함하여 출력한다는 것이다. 이렇게 되면 visit 배열을 만들어 방문여부를 체크하는 이유가 없어진다. 그냥 이중 for 루프를 돌리기만 하면 된다. 그 외에는 동일하다.
#include <iostream>
#include <vector>
using namespace std;
vector<int> v;
void permutation(int M, int N)
{
if(N == 0) {
for(vector<int>::iterator iter = v.begin(); iter < v.end(); ++iter) {
cout << *iter;
if(iter + 1 != v.end())
cout << ' ';
}
cout << endl;
return;
}
for(int i = 1; i < M + 1; ++i) {
v.push_back(i);
permutation(M, N - 1);
v.pop_back();
}
return;
}
int main()
{
int M, N;
cin >> M >> N;
permutation(M, N);
return 0;
}
4번
문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ … ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
예제 출력 1
1
2
3
예제 입력 2
4 2
예제 출력 2
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4
풀이
2번과 3번을 섞어놓은 문제다. 그러면 index를 구하는 loop문을 추가하되 visit 배열을 없애면 된다. 그 외에는 같다.
#include <iostream>
#include <vector>
using namespace std;
vector<int> v;
bool chosen[8] = {false};
void combination(int N, int M)
{
if(M == 0) {
for(vector<int>::iterator iter = v.begin(); iter < v.end(); ++iter)
cout << *iter << ' ';
cout << "\n";
return;
}
int index;
for(index = 8; index > 0; --index) {
if(chosen[index]) break;
}
for(int i = index; i < N + 1; ++i) {
v.push_back(i);
chosen[i] = true;
combination(N, M - 1);
v.pop_back();
chosen[i] = false;
}
return;
}
int main()
{
int N, M;
chosen[1] = true;
cin >> N >> M;
combination(N, M);
return 0;
}
5번
문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.
N개의 자연수 중에서 M개를 고른 수열 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
4 5 2
예제 출력 1
2
4
5
예제 입력 2
4 2
9 8 7 1
예제 출력 2
1 7
1 8
1 9
7 1
7 8
7 9
8 1
8 7
8 9
9 1
9 7
9 8
풀이
이제는 1부터 N까지가 아니라 주어진 배열들을 섞어서 출력해야 한다. 다른 건 없다. 출력용 vector를 하나 만들었다. 그 외에는 1번과 동일
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v;
int arr[8];
bool visited[8] = {false};
void permutation(int N, int M)
{
if(M == 0) {
for(vector<int>::const_iterator iter = v.begin(); iter < v.end(); ++iter)
cout << *iter << ' ';
cout << "\n";
return;
}
for(int i = 0; i < N; ++i) {
if(visited[i]) continue;
v.push_back(arr[i]);
visited[i] = true;
permutation(N, M - 1);
v.pop_back();
visited[i] = false;
}
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(NULL);
int N, M;
cin >> N >> M;
for(int i = 0; i < N; ++i)
cin >> arr[i];
sort(arr, arr + N);
permutation(N, M);
return 0;
}
6번
문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.
N개의 자연수 중에서 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
4 5 2
예제 출력 1
2
4
5
예제 입력 2
4 2
9 8 7 1
예제 출력 2
1 7
1 8
1 9
7 8
7 9
8 9
풀이
2번과 같다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v;
int arr[8];
bool visited[8] = {false};
void permutation(int N, int M)
{
if(M == 0) {
for(vector<int>::const_iterator iter = v.begin(); iter < v.end(); ++iter)
cout << *iter << ' ';
cout << "\n";
return;
}
int index;
for(index = N; index >= 0; --index)
if(visited[index]) break;
for(int i = index + 1; i < N; ++i) {
if(visited[i]) continue;
v.push_back(arr[i]);
visited[i] = true;
permutation(N, M - 1);
v.pop_back();
visited[i] = false;
}
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(NULL);
int N, M;
cin >> N >> M;
for(int i = 0; i < N; ++i)
cin >> arr[i];
sort(arr, arr + N);
permutation(N, M);
return 0;
}
7번
문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.
N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
4 5 2
예제 출력 1
2
4
5
예제 입력 2
4 2
9 8 7 1
예제 출력 2
1 1
1 7
1 8
1 9
7 1
7 7
7 8
7 9
8 1
8 7
8 8
8 9
9 1
9 7
9 8
9 9
풀이
3번과 같음
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v;
int arr[8];
void permutation(int N, int M)
{
if(M == 0) {
for(vector<int>::const_iterator iter = v.begin(); iter < v.end(); ++iter)
cout << *iter << ' ';
cout << "\n";
return;
}
for(int i = 0; i < N; ++i) {
v.push_back(arr[i]);
permutation(N, M - 1);
v.pop_back();
}
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(NULL);
int N, M;
cin >> N >> M;
for(int i = 0; i < N; ++i)
cin >> arr[i];
sort(arr, arr + N);
permutation(N, M);
return 0;
}
8번
문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.
N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ … ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
4 5 2
예제 출력 1
2
4
5
예제 입력 2
4 2
9 8 7 1
예제 출력 2
1 1
1 7
1 8
1 9
7 7
7 8
7 9
8 8
8 9
9 9
풀이
4번과 같음
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v;
int arr[8];
bool visited[8] = {false};
void permutation(int N, int M)
{
if(M == 0) {
for(vector<int>::const_iterator iter = v.begin(); iter < v.end(); ++iter)
cout << *iter << ' ';
cout << "\n";
return;
}
int index;
for(index = N; index > 0; --index)
if(visited[index]) break;
for(int i = index; i < N; ++i) {
//if(visited[i]) continue;
v.push_back(arr[i]);
visited[i] = true;
permutation(N, M - 1);
v.pop_back();
visited[i] = false;
}
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(NULL);
int N, M;
cin >> N >> M;
for(int i = 0; i < N; ++i)
cin >> arr[i];
sort(arr, arr + N);
permutation(N, M);
return 0;
}
9번
문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
N개의 자연수 중에서 M개를 고른 수열 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
4 4 2
예제 출력 1
2
4
예제 입력 2
4 2
9 7 9 1
예제 출력 2
1 7
1 9
7 1
7 9
9 1
9 7
9 9
풀이
여기가 진짜 어려웠는데, 순회과정을 그림으로 그려보면 대충 이렇다.
그림에도 나와있듯이 직전에 방문한 노드의 값과 같으면 출력하지 않아야 한다.
그걸 어떻게 구현하느냐… 어차피 넣고 빼고 하는 그 패턴 속에서 구현될 것이기 때문에 함수의 매개변수로 받지 않아도 괜찮다. 들어가자마자 continue 되는 것을 막기 위해 처음에는 prev = 0을 주고 재귀함수 패턴인 넣고 빼고 하는 과정에 prev를 저장하는 코드를 추가해주면 된다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//자기자신을 빼면서 중복되는 수는 빼주되 N에서 제외시키지 않아야 함
vector<int> v;
vector<int> arr;
bool visited[8] = {false};
void permutation(int N, int M, int cnt)
{
if(cnt == M) {
for(vector<int>::const_iterator iter = v.begin(); iter < v.end(); ++iter)
cout << *iter << ' ';
cout << "\n";
return;
}
int prev = 0; // 각 경우에서 첫 번째의 경우는 제외
for(int i = 0; i < N; ++i) {
if(visited[i] || prev == arr[i]) continue;
visited[i] = true;
v.push_back(arr[i]);
prev = v[cnt];
permutation(N, M, cnt + 1);
visited[i] = false;
v.pop_back();
}
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(NULL);
int N, M, tmp;
cin >> N >> M;
for(int i = 0; i < N; ++i) {
cin >> tmp;
arr.push_back(tmp);
}
sort(arr.begin(), arr.end());
permutation(N, M, 0);
return 0;
}
10번
문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
N개의 자연수 중에서 M개를 고른 수열 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ … ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
4 4 2
예제 출력 1
2
4
예제 입력 2
4 2
9 7 9 1
예제 출력 2
1 7
1 9
7 9
9 9
풀이
9번에서 index구하는 for 루프문을 추가한 케이스이다. 그 외에는 동일하다
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v;
vector<int> arr;
bool visited[8] = {false};
void permutation(int N, int M, int cnt)
{
if(cnt == M) {
for(vector<int>::const_iterator iter = v.begin(); iter < v.end(); ++iter)
cout << *iter << ' ';
cout << "\n";
return;
}
int index;
for(index = N; index > 0; --index)
if(visited[index]) break;
int prev = 0; // 각 경우에서 첫 번째의 경우는 제외
for(int i = index; i < N; ++i) {
if(visited[i] || prev == arr[i]) continue;
visited[i] = true;
v.push_back(arr[i]);
prev = v[cnt];
permutation(N, M, cnt + 1);
visited[i] = false;
v.pop_back();
}
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(NULL);
int N, M, tmp;
cin >> N >> M;
for(int i = 0; i < N; ++i) {
cin >> tmp;
arr.push_back(tmp);
}
sort(arr.begin(), arr.end());
permutation(N, M, 0);
return 0;
}
11번
문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
4 4 2
예제 출력 1
2
4
예제 입력 2
4 2
9 7 9 1
예제 출력 2
1 1
1 7
1 9
7 1
7 7
7 9
9 1
9 7
9 9
풀이
9번에서 visit 배열을 뺀 케이스이다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v;
vector<int> arr;
void permutation(int N, int M, int cnt)
{
if(cnt == M) {
for(vector<int>::const_iterator iter = v.begin(); iter < v.end(); ++iter)
cout << *iter << ' ';
cout << "\n";
return;
}
int prev = 0; // 각 경우에서 첫 번째의 경우는 제외
for(int i = 0; i < N; ++i) {
if(prev == arr[i]) continue;
v.push_back(arr[i]);
prev = v[cnt];
permutation(N, M, cnt + 1);
v.pop_back();
}
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(NULL);
int N, M, tmp;
cin >> N >> M;
for(int i = 0; i < N; ++i) {
cin >> tmp;
arr.push_back(tmp);
}
sort(arr.begin(), arr.end());
permutation(N, M, 0);
return 0;
}
12번
문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ … ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
4 4 2
예제 출력 1
2
4
예제 입력 2
4 2
9 7 9 1
예제 출력 2
1 1
1 7
1 9
7 7
7 9
9 9
풀이
다 쓰까
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//자기자신을 빼면서 중복되는 수는 빼주되 N에서 제외시키지 않아야 함
vector<int> v;
vector<int> arr;
void permutation(int N, int M, int cnt)
{
if(cnt == M) {
for(vector<int>::const_iterator iter = v.begin(); iter < v.end(); ++iter)
cout << *iter << ' ';
cout << "\n";
return;
}
int index;
if(v.size()){
for(index = 0; index < N; ++index)
if(v.back() == arr[index]) break;
}
else index = 0;
int prev = 0; // 각 경우에서 첫 번째의 경우는 제외
for(int i = index; i < N; ++i) { // 자기자신부터 시작하게 만들어야 됨
if(prev == arr[i]) continue;
v.push_back(arr[i]);
prev = v[cnt];
permutation(N, M, cnt + 1);
v.pop_back();
}
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(NULL);
int N, M, tmp;
cin >> N >> M;
for(int i = 0; i < N; ++i) {
cin >> tmp;
arr.push_back(tmp);
}
sort(arr.begin(), arr.end());
permutation(N, M, 0);
return 0;
}
끝
댓글남기기