[ 백준 15649 , 15650 ] N과M(1) , N과M(2) (C++)

백준의 N과M(1), (2) 문제이다.

( N과M(1) 바로가기 )

( N과M(2) 바로가기 )

N과 M 시리즈들은 모두 순열과 조합에 대한 문제들이다. 문제를 풀기 전, 순열과 조합의 개념을 잘 모르겠다면

조합 구현하기(Click) 와 순열 구현하기(Click) 에 있는 글들을 읽어보고 오자.

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

1) N과M(1)은 순열에 대한 구현을 하는 것이다. 위의 글을 읽어보고 왔다면 이 문제는 쉽게 풀 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 9
using namespace std;
 
int N, M;
bool Visit[MAX];
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 = 1; i <= N; i++)
    {
        if (Visit[i] == true) continue;
        Visit[i] = true;
        V.push_back(i);
        DFS(Cnt + 1);
        Visit[i] = false;
        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(2) 문제풀이]

1) 이 문제는 조합을 구현하는 문제이다. 사실, 문제만 읽어보면 순열인지 조합인지 무슨 수열을 출력하라는건지 잘 모를

   수 있는데, 문제 결과를 보고나, 고른 수열이 오름차순이어야 한다는 것은 절대로 선택한 숫자보다 작은 숫자들은

   나오면 안된다는 점에서 조합이라는 것을 눈치챌 수가 있다.

   ex) 조합에 대한 설명 글에서 { 1, 2, 3 } 을 뽑았으면, 시작점이 '2'가 되는순간 2보다 더 작은 1은 쳐다도 보지 않는다고

       말했음. 즉, 오름차순으로 뽑아야 한다 = '2'를 뽑았으면 더 작은 '1'은 쳐다도 보지 않는다. 라는 점에서

       조합이라는 것을 눈치채자 !

   마찬가지로 위의 글을 읽어보고 왔다면 너무나도 쉽게 풀 수 있는 문제이다.

[ 소스코드 ]

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