[ 백준 15654 , 15655 ] N과M(5) , N과M(6) (C++)

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

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

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

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

1) 이 문제는 실행결과를 보면 알 수 있지만, 순열을 구하는 문제이다. 중복을 허용하는 중복순열이 아닌 일반 수열이다.

   혹시 순열에 대해서 잘 모르시는 분들은 아래의 링크를 타고 글을 읽고 오길 바란다.

   [ 순열 구체적으로 알아보기 ]

  

   순열의 기본적인 구현은 위의 글을 읽고 왔다면 이해를 했을거라 생각한다. 이 문제를 풀 때 주의해야 할 점에 대해서만

   알아보자. 우리가 이 문제를 입력받은 그대로 순열을 출력해보면, 아마 예제 출력처럼 깔끔하게 나오지 않는다는 것을

   확인할 수 있다. 왜냐하면, 이 문제에서는 출력을 "사전순으로 증가하는 순서로 출력하세요" 라고 했기 때문이다.

   따라서, 숫자를 입력받아서 배열에 저장하든 벡터에 저장하든, 정렬을 통해서 오름차순으로 만들어준 후에, 순열을

   구현한다면 정답을 도출해낼 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<vector>
 
#define endl "\n"
#define MAX 8
using namespace std;
 
int N, M;
int Arr[MAX];
bool Selec[MAX];
vector<int> V;
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        cin >> Arr[i];
    }
    sort(Arr, Arr + N);
}
 
void Select(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++)
    {
        if (Selec[i] == true) continue;
        Selec[i] = true;
        V.push_back(Arr[i]);
        Select(Cnt + 1);
        V.pop_back();
        Selec[i] = false;
    }
}
 
void Solution()
{
    Select(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(6) 문제풀이 ]

1) 이 문제는 실행결과를 보면 일반 조합을 구하는 문제이다. 이전의 N과M 시리즈에서도 조합을 구하는 문제가 있었는데,

   그 때의 문제들과 다른점은, 그 때는 수열에 들어가는 원소들의 입력을 오름차순으로 입력받을 수 있었는데, 지금은 기존의

   수열이 오름차순이 아니라는 것이다. { 4, 5, 2 } 이런 식으로 순서에 없이 랜덤적으로 데이터를 입력받아야 한다.

   우리는 이러한 수열들을 오름차순으로 출력시키기 위해서는 입력받은 데이터들을 정렬시키고 문제를 풀면 된다.

   [ 조합 구체적으로 알아보기(Click) ]

   [ N과M(2) 문제풀이 보러가기 (조합 구하는 문제) ]

[ 소스코드 ]

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