[ 백준 15663 , 15664 ] N과M(9) , N과M(10) (C++)

백준의 N과M시리즈 (9), (10) 문제이다.

[ N과M(9) 문제 바로가기 ]
[ N과M(10) 문제 바로가기 ]

[ 순열 구현하기 자세히 알아보기 ]

[ 조합 구현하기 자세히 알아보기 ]

[ N과M(9) 문제풀이 ]

1) 이 문제는 일반 순열을 출력하는 문제이다. 먼저 순열에 대해서 잘 모른다면 이 글의 제일 위에 있는 순열 자세히 알아보기

   글을 링크를 타고 읽고 오도록 하자.

   글을 읽고 와서 그대로 구현을 했다면, 실행결과가 정답과 다르게 나온다는 것을 알 수 있을 것이다.

   먼저 다르게 나오는 이유는 2가지가 있다. 위의 링크에 있는 순열을 구현하는 코드는 이미 오름차순으로 정렬이 되어있는

   배열을 가지고 구현을 하기 때문이다. 즉, 이 문제에서 입력받아서 데이터들을 저장해두는 배열 혹은 벡터를 애초에

   정렬을 시킨다면 정답과 비슷하게 나올 것이다. 하지만, 정답과 똑같이 나오지는 않을 것이다.

   왜냐하면, 이 문제에서는 중복 체크를 해줘야 하기 때문이다.

   문제에 있는 예제입력1을 한번 보자. { 4, 4, 2 } 가 입력된 데이터들이고, 여기서 한개를 골라 순열을 만들어서 출력한다면

   { 2, 4, 4 } 가 나오게 될 것이다. 이 때, 4가 중복되어 버리는 것이다.

   따라서 이 중복되는 것에 대한 처리를 해줘야 한다. 본인은 순열을 구현함에 있어 현재 선택된 원소들을 Vector에 저장해

   주었다.

   M개 만큼 모두 골랐다면, 현재 Vector에 들어있는 값들을 string으로 만들어 주었다.

   string으로 만든 이후, set을 사용해서 중복 체크를 해주었다. { 2, 4, 4 } 이 경우만 보고 왜 string으로 만들었는지

   이해가 안되는 사람이 있을 수도 있다. 예제 입력 2번 같은 경우에는 2개를 뽑아야 한다.

   즉, 그 2개를 합쳐서 { 1, 7 } 이면 "17"이라는 string으로 만들어서 중복 체크를 해준 것이다.

   입력받은 데이터를 정렬시키고, 중복체크까지 해준다면 정답을 도출해 낼 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
 
#define endl "\n"
#define MAX 8
using namespace std;
 
int N, M;
int Arr[MAX];
bool Select[MAX];
 
vector<int> V;
set<string> Visit;
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        cin >> Arr[i];
    }
    sort(Arr, Arr + N);
}
 
bool Duplicate()
{
    string Temp = "";
    for (int i = 0; i < V.size(); i++)
    {
        char A = V[i] + '0';
        Temp = Temp + A;
    }
 
    if (Visit.find(Temp) == Visit.end())
    {
        Visit.insert(Temp);
        return false;
    }
    else
    {
        return true;
    }
}
 
void DFS(int Cnt)
{
    if (Cnt == M)
    {
        if (Duplicate() == false)
        {
            for (int i = 0; i < V.size(); i++)
            {
                cout << V[i] << " ";
            }
            cout << endl;
        }
        return;
    }
 
    for (int i = 0; i < N; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        V.push_back(Arr[i]);
        DFS(Cnt + 1);
        V.pop_back();
        Select[i] = false;
    }
}
 
void Solution()
{
    DFS(0);
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}

[ N과M(10) 문제풀이 ]

1) 이 문제는 일반 조합을 문제이다. 조합을 구현하는 방법을 잘 모른다면 이 글에 제일 위에 있는 조합 자세히 알아보기 글을

   읽어 보고 오도록 하자.

   N과M(9) 문제와 마찬가지로, 조합을 출력하면서 중복을 체크해줘야 한다. 중복을 체크하는 방식은 N과M(9) 와

   동일하게 체크를 해줬으니, N과M(9)의 설명을 읽고 온다면 중복 체크도 쉽게 할 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<set>
#include<algorithm>
 
#define endl "\n"
#define MAX 8
using namespace std;
 
int N, M;
int Arr[MAX];
bool Select[MAX];
 
set<string> Visit;
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        cin >> Arr[i];
    }
    sort(Arr, Arr + N);
}
 
void Check()
{
    string Tmp = "";
    for (int i = 0; i < N; i++)
    {
        if (Select[i] == true)
        {
            char C = Arr[i] + '0';
            Tmp = Tmp + C;
        }
    }
 
    if (Visit.find(Tmp) == Visit.end())
    {
        Visit.insert(Tmp);
        for (int i = 0; i < N; i++)
        {
            if (Select[i] == true)
            {
                cout << Arr[i] << " ";
            }
        }
        cout << endl;
    }
}
 
void DFS(int Idx, int Cnt)
{
    if (Cnt == M)
    {
        Check();
        return;
    }
 
    for (int i = Idx; i < N; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        DFS(i, Cnt + 1);
        Select[i] = false;
    }
}
 
void Solution()
{
    DFS(0, 0);
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}