N과 M(Α~Ω)
백준에는 N과 M이라는 시리즈문제가 12 있다. 순열과 조합에 익숙하지 않은 사람들에게 추천하는 문제들이며
nPm, nΠm과 같은 조합을 구현하는 문제들이다. 오늘은 한 함수를 조금씩만 변형하여 이 문제들을 해결해보려고 한다.
함수의 원형은 다음과 같다.
void solve(int n, int k, int m);
- 매개변수를 잠시 살펴보자!
- 여기서 n은 조합을 저장하는 배열의 index이다.
- k는 조합의 크기이다.
- m은 내가 사용할 수 있는 숫자의 개수이다.
이제 Problem을 살펴보자
쉽게 말해 nPm을 구하는 문제이다. 이에 맞춰서 solve함수의 body를 완성해보자.
solve함수를 재귀로 작성할 것이기 때문에 종단조건을 먼저 설정하자.
if(n==k)
{
for(int i=0;i<k;i++)
{
cout<<comb[i]<<" ";
}
cout<<'\n';
return;
}
이제 나머지 부분을 생각해보자. comb에는 한 번 들어갔던 숫자를 다시 넣으면 안 되기 때문에
주어진 숫자들을 내가 사용한 적이 있는지 체크할 필요가 있다. 또 순서가 뒤죽박죽이기 때문에
m개의 숫자들을 매번 확인해보아야 한다. 즉,
for(int i=0;i<m;i++)
{
if(used[i]==0) // 사용한 적이 없는 숫자이면
{
comb[n] = arr[i]; //comb의 n번째 위치에 그 숫자를 넣고
used[i] = 1; //사용했다 표시를 한다.
solve(n+1,k,m); //그 다음 comb를 기록한다.
//여기까지 왔으면 한 개의 조합을 print한 뒤일 것이다.
used[i] = 0; //마지막으로 사용한 숫자를 comb에서 제거해준다.
}
}
1번을 풀었으면 12문제 다 풀었다고 얘기해도 과언이 아니다. 나머지 문제들도 간단히 정리해보자.
void solve1(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 1~N nPm
void solve2(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 1~N nPm 오름차순
void solve3(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 1~N nΠm
void solve4(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 1~N nΠm 비내림차순
void solve5(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 arr nPm 오름차순(solve1과 동일)
void solve6(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 arr nPm 오름차순(solve2와 동일)
void solve7(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 arr nΠm (solve3와 동일)
void solve8(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 arr nΠm 비내림차순(solve4와 동일)
void solve9(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 중복된 arr nPm 중복금지
void solve10(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 중복된 arr nPm 비내림차순 중복금지
void solve11(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 중복된 arr nΠm(solve3와 동일)
void solve12(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 중복된 arr nΠm(solve4와 동일) 비내림차순
nΠm의 경우 used를 사용하지 않으면 해결할 수 있다.
비내림차순의 경우 조금의 수정으로 해결할 수 있다.
for(int i=0;i<m;i++)
{
if (n > 0 && comb[n - 1] > arr[i])
{
continue;
}
if(used[i]==0)
{
comb[n] = arr[i];
used[i] = 1;
solve(n + 1, k, m);
used[i] = 0;
}
}
여기서 10번은 똑같은 조합을 두 번 이상 출력하면 안 되는 조건이 있기 때문에 조금 더 생각해야한다. 예를 들어보자. arr = [1, 9, 9]가 있고 M = 2이다. 1번 문제처럼 풀게 되면 다음과 같다.
arr = [`1`, 9, 9] comb = [1]
arr = [`1`, `9`, 9] comb = [1, 9] => print()
arr = [`1`, 9, `9`] comb = [1, 9] => print()
!!!? 이럴수가 [1,9]가 두 번 print()된다. 어떻게 하면 이런 불상사를 막을 수 있을까?
방법은 간단하다. comb에 추가하려는 숫자의 이전 숫자가 used가 아니면서 나와 동일한 숫자이면
comb에 추가하지 않으면 된다.
if (i > 0 && (used[i - 1] == 0 && arr[i - 1] == arr[i]))
{
continue;
}
한 시간정도 문제를 풀었던 것같다. 여러분은 훨씬 더 빠를 것이다. 마지막으로 전체 코드를 남긴다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, tmp;
int used[10001];
int comb[10001];
int arr[10001];
int visited[10001];
vector<int>arr2;
void solve1(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 1~N nPm
void solve2(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 1~N nPm 오름차순
void solve3(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 1~N nΠm
void solve4(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 1~N nΠm 비내림차순
void solve5(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 arr nPm 오름차순(solve1과 동일)
void solve6(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 arr nPm 오름차순(solve2와 동일)
void solve7(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 arr nΠm (solve3와 동일)
void solve8(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 arr nΠm 비내림차순(solve4와 동일)
void solve9(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 중복된 arr nPm 중복금지
void solve10(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 중복된 arr nPm 비내림차순 중복금지
void solve11(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 중복된 arr nΠm(solve3와 동일)
void solve12(int n, int k, int m); // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 중복된 arr nΠm(solve4와 동일) 비내림차순
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
for (int i = 0; i < N; i++)
{
cin >> tmp;
arr2.push_back(tmp);
}
sort(arr2.begin(), arr2.end());
arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());
//for (int i = 0; i < N; i++)
//{
// arr[i] = i + 1;
// cin >> arr[i];
//}
//sort(arr, arr + N);
solve12(0, M, arr2.size());
return 0;
}
void solve1(int n, int k, int m)
{
if (n == k)
{
for (int i = 0; i < k; i++)
{
cout << comb[i] << ' ';
}
cout << '\n';
}
else
{
for (int i = 0; i < m; i++)
{
if (used[i] == 0)
{
used[i] = 1;
comb[n] = arr[i];
solve1(n + 1, k, m);
used[i] = 0;
}
}
}
}
void solve2(int n, int k, int m)
{
if (n == k)
{
for (int i = 0; i < k; i++)
{
cout << comb[i] << ' ';
}
cout << '\n';
}
else
{
for (int i = 0; i < m; i++)
{
if (used[i] == 0)
{
used[i] = 1;
if (n > 0)
{
if (comb[n - 1] < arr[i])
{
comb[n] = arr[i];
solve2(n + 1, k, m);
}
}
else
{
comb[n] = arr[i];
solve2(n + 1, k, m);
}
used[i] = 0;
}
}
}
}
void solve3(int n, int k, int m)
{
if (n == k)
{
for (int i = 0; i < k; i++)
{
cout << comb[i] << ' ';
}
cout << '\n';
}
else
{
for (int i = 0; i < m; i++)
{
comb[n] = arr[i];
solve3(n + 1, k, m);
}
}
}
void solve4(int n, int k, int m) // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수
{
if(n == k)
{
for (int i = 0; i < k; i++)
{
cout << comb[i] << ' ';
}
cout << '\n';
}
else
{
for(int i=0;i<m;i++)
{
if (n > 0)
{
if (comb[n - 1] <= arr[i])
{
comb[n] = arr[i];
solve4(n + 1, k, m);
}
}
else
{
comb[n] = arr[i];
solve4(n + 1, k, m);
}
}
}
}
void solve5(int n, int k, int m) // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 arr nPm (solve1과 동일)
{
if (n == k)
{
for (int i = 0; i < k; i++)
{
cout << comb[i] << ' ';
}
cout << '\n';
}
else
{
for (int i = 0; i < m; i++)
{
if (used[i] == 0)
{
used[i] = 1;
comb[n] = arr[i];
solve5(n + 1, k, m);
used[i] = 0;
}
}
}
}
void solve6(int n, int k, int m) // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 arr nPm 오름차순(solve2와 동일)
{
if (n == k)
{
for (int i = 0; i < k; i++)
{
cout << comb[i] << ' ';
}
cout << '\n';
}
else
{
for (int i = 0; i < m; i++)
{
if (used[i] == 0)
{
used[i] = 1;
if (n > 0)
{
if (comb[n - 1] < arr[i])
{
comb[n] = arr[i];
solve6(n + 1, k, m);
}
}
else
{
comb[n] = arr[i];
solve6(n + 1, k, m);
}
used[i] = 0;
}
}
}
}
void solve7(int n, int k, int m) // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 arr nΠm (solve3와 동일)
{
if (n == k)
{
for (int i = 0; i < k; i++)
{
cout << comb[i] << ' ';
}
cout << '\n';
}
else
{
for (int i = 0; i < m; i++)
{
comb[n] = arr[i];
solve3(n + 1, k, m);
}
}
}
void solve8(int n, int k, int m) // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 arr nΠm 비내림차순(solve4와 동일)
{
if (n == k)
{
for (int i = 0; i < k; i++)
{
cout << comb[i] << ' ';
}
cout << '\n';
}
else
{
for (int i = 0; i < m; i++)
{
if (n > 0)
{
if (comb[n - 1] <= arr[i])
{
comb[n] = arr[i];
solve4(n + 1, k, m);
}
}
else
{
comb[n] = arr[i];
solve4(n + 1, k, m);
}
}
}
}
void solve9(int n, int k, int m) // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 중복된 arr nPm
{
if (n == k)
{
for (int i = 0; i < k; i++)
{
cout << comb[i] << ' ';
}
cout << '\n';
}
else
{
for (int i = 0; i < m; i++)
{
if (used[i] == 0)
{
used[i] = 1;
if (i > 0)
{
if (used[i - 1] != 0 || arr[i - 1] != arr[i])
{
comb[n] = arr[i];
solve9(n + 1, k, m);
}
}
else
{
comb[n] = arr[i];
solve9(n + 1, k, m);
}
used[i] = 0;
}
}
}
}
void solve10(int n, int k, int m) // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 중복된 arr nPm 비내림차순 중복금지
{
if (n == k)
{
for (int i = 0; i < k; i++)
{
cout << comb[i] << ' ';
}
cout << '\n';
}
else
{
for (int i = 0; i < m; i++)
{
if (used[i] == 0)
{
if (n > 0 && comb[n - 1] > arr[i])
{
continue;
}
if (i > 0 && (used[i - 1] == 0 && arr[i - 1] == arr[i]))
{
continue;
}
comb[n] = arr[i];
used[i] = 1;
solve10(n + 1, k, m);
used[i] = 0;
}
}
}
}
void solve11(int n, int k, int m) // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 중복된 arr nΠm(solve3와 동일)
{
if (n == k)
{
for (int i = 0; i < k; i++)
{
cout << comb[i] << ' ';
}
cout << '\n';
}
else
{
for (int i = 0; i < m; i++)
{
comb[n] = arr2[i];
solve11(n + 1, k, m);
}
}
}
void solve12(int n, int k, int m) // n : 고른 숫자를 저장할 위치, k : 골라야 할 숫자의 개수, m : 고를 수 있는 숫자의 개수 중복된 arr nΠm(solve4와 동일) 비내림차순
{
if (n == k)
{
for (int i = 0; i < k; i++)
{
cout << comb[i] << ' ';
}
cout << '\n';
}
else
{
for (int i = 0; i < m; i++)
{
if (n > 0)
{
if (comb[n - 1] <= arr2[i])
{
comb[n] = arr2[i];
solve12(n + 1, k, m);
}
}
else
{
comb[n] = arr2[i];
solve12(n + 1, k, m);
}
}
}
}