[ 백준 15665 , 15666 ] N과M(11) , N과M(12) (C++)

백준의 N과M 시리즈 (11), (12) 번 문제이다.

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

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

아직 조합 / 순열 / 중복조합 / 중복순열 에 대한 개념을 잘 모른다면 아래 링크를 타고 글을 읽고 오자 !!

[ 조합 구현하는 법 알아보기 ]

[ 순열 구현하는 법 알아보기 ]

[ 중복조합 구현하는 법 알아보기 ]

[ 중복순열 구현하는 법 알아보기 ]

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

1) 이 문제는 중복순열을 출력하는 문제이다. 중복순열에 대한 기본적인 개념과 구현방법은 위의 링크를 타고 읽고 오자.

   위의 링크를 읽고 와서 구현하더라도, 정답과 다르게 나올 것이다.

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

   예제입력에서 { 4, 4, 2 }가 있으면, { 2, 4, 4, } 가 나올 것인데, 4는 중복이기 때문에 한번 빼줘야 한다.

   본인은 이 부분을 처리해주기 위해서 string과 set을 사용해주었다.

   만약, 4를 선택해서 출력해야 될 경우라면, 4를 "4"라는 문자열로 만들어주어서, 중복체크를 해 주었다.

   사실, 숫잔데 굳이 string으로 만든 이유를 모르시겠는 분들은 1개를 뽑는 것이 아닌, 2개 이상의 값들에 대해서 생각해보면

   된다.

   예제입력2를 예시로 들면, { 9 , 7 , 9, 1 } 로 수열이 주어졌고, 이를 중복순열을 출력하다보면

   { 1, 9 } 가 2번 출력될 것이다. 왜냐하면 9가 2개이기 때문에, 컴퓨터 입장에서는 서로 다른 9를 사용했기 때문에

   다른 순열로 판단하고 { 1, 9 } 가 2개가 나올 것이다. 이를 string으로 만들어주면 "19" 라는 string이 되고

   이 문자열을 한번 방문했으면 더 이상 출력하지 않도록 구현해 주었다.

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<string>
#include<set>
 
#define endl "\n"
#define MAX 7
using namespace std;
 
int N, M;
int Arr[MAX];
int 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 DFS(int Cnt)
{
    if (Cnt == M)
    {
        string Temp = "";
        for (int i = 0; i < M; i++)
        {
            char C = Select[i] + '0';
            Temp = Temp + C;
        }
 
        if (Visit.find(Temp) == Visit.end())
        {
            Visit.insert(Temp);
            for (int i = 0; i < M; i++)
            {
                cout << Select[i] << " ";
            }
            cout << endl;
        }
        return;
    }
 
    for (int i = 0; i < N; i++)
    {
        Select[Cnt] = Arr[i];
        DFS(Cnt + 1);
    }
}
 
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(12) 문제풀이 ]

1) 이 문제는 중복조합을 출력하는 문제이다. 중복 조합에 대한 설명은 위의 링크를 참고하면 되고, 이 또한 N과M(11) 처럼

   중복을 처리해주는 과정이 필요하다. 중복 처리해주는 과정은 위의 풀이인 N과M(11) 풀이에서 구체적으로 했으므로

   생략하겠다.

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<string>
#include<set>
 
#define endl "\n"
#define MAX 8
using namespace std;
 
int N, M;
int Arr[MAX];
int 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 DFS(int Idx, int Cnt)
{
    if (Cnt == M)
    {
        string Temp = "";
        for (int i = 0; i < M; i++)
        {
            char C = Select[i] + '0';
            Temp = Temp + C;
        }
 
        if (Visit.find(Temp) == Visit.end())
        {
            Visit.insert(Temp);
            for (int i = 0; i < M; i++)
            {
                cout << Select[i] << " ";
            }
            cout << endl;
        }
        return;
    }
 
    for (int i = Idx; i < N; i++)
    {
        Select[Cnt] = Arr[i];
        DFS(i, Cnt + 1);
    }
}
 
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;
}