백준 N과 M (1) ~ (5) 복습

오늘은 N과 M 시리즈를 다시 풀어보았습니다. 백트래킹(완전탐색)은 BFS, DFS에서도 굉장히 많이 응용되어서 나오기 때문에 잘 알아둬야 할 것 같습니다. 문제마다 조금씩 다른 유형이지만, 조건을 잘 보고 로직을 조금씩 다듬으면 수월하게 풀 수 있을 것 같다고 생각합니다. 

1번부터 5번까지 문제 설명 드리겠습니다.

(공통) 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1 : 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

2: 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열, 고른 수열은 오름차순이어야 한다.

3: 1부터 N까지 자연수 중에서 M개를 고른 수열, 같은 수를 여러 번 골라도 된다.

4: 1부터 N까지 자연수 중에서 M개를 고른 수열, 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

5: N개의 자연수 중에서 M개를 고른 수열

<코드>

1번 

#include <iostream>

using namespace std;
bool check[9] = {0};
int num[9];
int n,m;

void print(int idx)
{
    if(idx == m)
    {
        for(int i=0;i<m;i++)
        {
            cout<<num[i]<<' ';
        }
        cout<<'\n';
        return;
    }

    for(int i=1;i<=n;i++)
    {
        if(!check[i])
        {
            check[i] = true;
            num[idx] = i;
            print(idx+1);
            check[i] = false;
        }
    }
}

int main()
{
    cin>>n>>m;
    print(0);

    return 0;
}

1,2 번에는 중복을 허용하지 않기 때문에 check변수를 통해 해당 숫자가 사용이 되었는지 확인해줘야 합니다.

2번

#include <iostream>

using namespace std;
bool check[9];
int num[9];
int n,m;

void print(int idx, int start)
{
    if(idx == m)
    {
        for(int i=0;i<m;i++)
        {
            cout<<num[i]<<' ';
        }
        cout<<'\n';
        return;
    }
    for(int i=start;i<=n;i++)
    {
        if(check[i]) continue;
        // 사용되었으면 pass (오름차순으로 나타내기 위한 방법)
        if(!check[i])
        {
            check[i] = true;
            num[idx] = i;
            print(idx+1,i+1);
            check[i] = false;
        }
    }
}

int main()
{
    cin>>n>>m;
    print(0, 1);
    return 0;
}

2번의 경우는 오름차순으로 순열을 나타내기 위해 if(check[i]) continue; 부분을 걸어주었습니다. 더불어 시작점도 매개변수에 넣어줬습니다. 

3번

#include <iostream>

using namespace std;
int n, m;
bool check[9];
int num[9];

void print(int idx)
{
    if(idx == m)
    {
        for(int i=0;i<m;i++)
        {
            cout<<num[i]<<' ';
        }
        cout<<'\n';
        return;
    }

    for(int i=1;i<=n;i++)
    {
        check[i] = true;
        num[idx] = i;
        print(idx+1);
        check[i] = false;
    }
}

int main()
{
    cin>>n>>m;
    print(0);
}

4번

#include <iostream>

using namespace std;
int n, m;
int num[9];
int check[9];

void print(int idx)
{
    if(idx == m)
    {
        for(int i=1;i<m;i++)
        {
            if(num[i]<num[i-1]) return;
        }
        
        for(int i=0;i<m;i++)
        {
            cout<<num[i]<<' ';
        }
        cout<<'\n';
        return;
    }
    for(int i=1;i<=n;i++)
    {

        check[i] = true;
        num[idx] = i;
        print(idx+1);
        check[i] = false;
    }
}

int main()
{
    cin>>n>>m;
    print(0);
}

5번

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int n, m;
bool check[9];
int num[9];
int result[9];

void print(int idx)
{
    if(idx == m)
    {
        for(int i=0;i<m;i++)
        {
            cout<<result[i]<<' ';
        }
        cout<<'\n';
        return;
    }
    for(int i=0;i<n;i++)
    {
        if(check[i]) continue;
        check[i] = true;
        result[idx] = num[i];
        print(idx+1);
        check[i] = false; 
    }
   
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>num[i];
    }
    sort(num, num+n);

    print(0);

    return 0;
    


}

질문 및 지적 모두 환영합니다. 저는 함수를 짤 때, 매개변수를 적게 두고 푸는 것을 좋아하는데 가독성 측면에서 조금 떨어져보이네요. 이상 포스팅 마치겠습니다.