[C++] Boj 15650 N과 M (2)

문제 링크

15650 N과 M (2)

 

접근

N과 M (1) 문제를 조금 변형한 문제이다. 조건이 하나 추가되었다.

• 고른 수열은 오름차순이어야 한다.

예를 들어, (1, 2), (1, 3)은 되지만 (2, 1), (3, 1)은 안 된다. 이미 뽑은 숫자가 다음 뽑을 숫자보다 크면 백트래킹을 진행하지 못하게 막아 주면 된다. 따라서 백트래킹을 하기 전에 다음 조건문을 추가하여 오름차순인 수열만 얻을 수 있게끔 필터링했다.

        // 오름차순인 수열만을 출력하기 위해
        // (1, 2) (1, 3) 은 되지만 (3, 1), (2, 1)은 안 되므로
        // 이미 뽑은 숫자가 다음 뽑을 숫자보다 크면 진행하지 못하도록 했다.
        if (numberCount > 0 && numbers[numberCount - 1] > i + 1) continue;

 

전체 코드

#include<iostream>
using namespace std;

// 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램

int N, M;

int numbers[10];
int isUsed[10];

void Solve(int numberCount)
{
    // 중복 없이 M 개를 다 골랐을 경우
    if (numberCount == M)
    {
        for (int i = 0; i < M; i++)
        {
            cout << numbers[i] << ' ';
        }
        cout << '\n';
        return;
    }

    for (int i = 0; i < N; i++)
    {
        // 이미 방문했을 경우 그 수를 더 방문하지 않는다. 
        if (isUsed[i]) continue;

        // 오름차순인 수열만을 출력하기 위해
        // (1, 2) (1, 3) 은 되지만 (3, 1), (2, 1)은 안 되므로
        // 이미 뽑은 숫자가 다음 뽑을 숫자보다 크면 진행하지 못하도록 했다.
        if (numberCount > 0 && numbers[numberCount - 1] > i + 1) continue;

        // 백트래킹 
        isUsed[i] = true;
        numbers[numberCount] = i + 1;
        Solve(numberCount + 1);
        isUsed[i] = false;
    }

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    Solve(0);

    return 0;
}

 

next_permutation 함수

순열과 조합을 깔끔하게 해결할 수 있는 함수이다. 이 함수는 현재의 수열을 사전 순으로 생각했을 때의 다음 수열로 만들고  true를 반환하는 함수이다. 현재 1, 2, 3이라면 next_permutation을 실행한 후 1, 3, 2가 되고 next_permutation를 한 번 더 실행하면 2, 1, 3이 된다. 만약 현재의 수열이 사전순으로 생각했을 때 제일 마지막이어서 다음 수열이 존재하지 않는다면 false를 반환한다. 그렇기 때문에 do-while문으로 작성하면 코드가 깔끔하게 떨어진다. 또한 중복된 수가 있다고 해도 사전순의 결과를 잘 돌려준다. 

 

 

사용 예시 (모든 순열 구하기)

#include <iostream>
#include <algorithm> // next_permutation
using namespace std;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int a[3] = { 1, 2, 3 };
    do
    {
        for (int i = 0; i < 3; i++)
            cout << a[i];
        cout << '\n';
    } while (next_permutation(a, a + 3));

    return 0;
}

사용 예시 (조합)

1, 2, 3, 4에서 수 2개를 순서 없이 뽑는 모든 경우 출력

#include <iostream>
#include <algorithm> // next_permutation
using namespace std;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int a[4] = { 0, 0, 1, 1 };
    do
    {
        for (int i = 0; i < 4; i++)
            if (a[i] == 0)
                cout << i + 1;
        cout << '\n';
    } while (next_permutation(a, a + 4));

    return 0;
}

 

15650 문제를  next_permutation을 사용해서 풀어보기

#include <iostream>
#include <algorithm> // next_permutation
using namespace std;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int N, M;
    cin >> N >> M;

    int numbers[10] = {}; // 0 1 1 (N == 3, M == 1)
    // N은 몇개 중~
    // M은 몇개를 뽑느냐
    for (int i = N; i > M; i--)
        numbers[i - 1] = 1;
    
    do
    {
        for (int i = 0; i < N; i++)
            if (numbers[i] == 0)
                cout << i + 1 << ' ';
        cout << '\n';
    } while (next_permutation(numbers, numbers + N));

    return 0;
}