[ 백준 15656 , 15657 ] N과M(7) , N과M(8) (C++)

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

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

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

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

1) 이 문제는 중복순열을 구현해야 하는 문제이다. 중복순열을 구하는 방법은 아래의 링크를 타면 자세히 알 수 있다.

   [ 중복순열 구현하기(Click) ]

   중복순열을 구하는 방법은 위와 같다. 이 문제에서 신경 써줘야 할 점은, 수열은 사전순으로 출력해줘야 하므로

   기존의 값들을 저장하는 배열 혹은 벡터를 정렬을 시켜준 후, 출력한다면 사전순으로 출력이 가능하다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<algorithm>
 
#define endl "\n"
#define MAX 7
using namespace std;
 
int N, M;
int Arr[MAX];
vector<int> V;
 
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)
    {
        for (int i = 0; i < V.size(); i++)
        {
            cout << V[i] << " ";
        }
        cout << endl;
        return;
    }
 
    for (int i = 0; i < N; i++)
    {
        V.push_back(Arr[i]);
        DFS(Cnt + 1);
        V.pop_back();
    }
}
 
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(8) 문제풀이 ]

1) 이 문제는 중복조합에 대한 문제이다. 중복조합을 구하는 방법은 아래의 링크를 타고 읽어오면 구체적으로 알 수 있다.

   [ 중복조합 구현하기(Click) ]

   중복 조합을 구하는 방법은 위와 같다. 마찬가지로, 사전순으로 출력해야 하므로, 기존의 값들을 저장하는 배열 혹은

   벡터를 정렬시키고 구현한다면 원하는 결과를 얻을 수 있다.

[ 소스코드 ]

#include<iostream>
#include<algorithm>
 
#define endl "\n"
#define MAX 8
using namespace std;
 
int N, M;
int Arr[MAX];
int Select[MAX];
 
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)
    {
        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;
}