[ 백준 15651 , 15652 ] N과M(3) , N과M(4) (C++)

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

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

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

[ 조합 자세하게 알아보기(Click) ]

[ 순열 자세하게 알아보기(Click) ]

* 문제를 풀기 전, 순열과 조합에 대해서 부족하다고 생각하시는 분들은 위의 글을 읽고 오시기 바랍니다 ! *

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

1) 이 문제는 주어진 값들의 순열을 구하는 문제이다. 위의 글을 읽고 왔다면 이 문제는 쉽게 풀 수 있는 문제이다.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
using namespace std;
 
int N, M;
vector<int> V;
 
void Input()
{
    cin >> N >> M;
}
 
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(i + 1);
        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 (4) 문제풀이 ]

1) 이 문제는 중복 조합을 모두 출력해야 하는 문제이다. 같은 숫자를 한 번 이상 뽑으면서 순서는 상관이 없는 조합을 모두

   찾아내야 하는 문제이다.

   { 1, 1 } = 가능. (1을 2번 뽑는 것은 가능)

   { 1, 4 } , { 4, 1 } = 불가능.

   {1 , 4 } 를 뽑았으면, 1과 4를 뽑은 조합이 이미 생성된 것이므로, { 4, 1 } 은 이미 나온 조합으로 간주 !

   중복조합에 대한 자세한 설명은 아래의 글을 읽고 오자 !

   [ 중복조합에 대해 구체적으로 알아보기(Click) ]

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
using namespace std;
 
int N, M;
vector<int> V;
 
void Input()
{
    cin >> N >> M;
}
 
bool Can_Print()
{
    for (int i = 0; i < V.size() - 1; i++)
    {
        if (V[i] > V[i + 1]) return false;
    }
    return true;
}
 
void DFS(int Cnt)
{
    if (Cnt == M)
    {
        if (Can_Print() == true)
        {
            for (int i = 0; i < V.size(); i++)
            {
                cout << V[i] << " ";
            }
            cout << endl;
        }
        return;
    }
 
    for (int i = 0; i < N; i++)
    {
        V.push_back(i + 1);
        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;
}