[BOJ] 15649 : N과 M(1) - next_permutation 풀이 / C++

기존 백트래킹으로 풀었던 문제를 C++의 STL 중 하나인 next_permutation을 이용해 풀이해 보았다.

 

문제

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

풀이에 사용되는 next_permutation에 대해 정리한 링크이다.

https://taehun0933.tistory.com/18

[알고리즘] next_permutation - 순열과 조합 / C++

 

아이디어

1. 조합과 순열의 관점에서 볼 때 해당 문제는
n개 중 m개를 '선택'한 후, 선택된 수들을 '나열'해주는 것.

2. 때문에 next_permutation을 두 번 이용하여
첫 번째는 조합의 방식으로 사용, 원소들을 선택해 주고
두 번째는 순열의 방식으로 사용, 선택된 원소를 나열해 주었다.

3. 선택된 원소를 나열하는 과정에서 바로 출력 시
특정 조합 -> 그 조합의 사전 순 출력 -> 다음 조합으로 반복.
때문에 결과적으로는 사전 순으로의 출력이 아니게 된다.
때문에 완성된 순열을 일단 벡터에 저장해 주고,
마지막에 해당 벡터를 사전 순으로 정렬하여 출력해 주었다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<vector<int>> res;
// 완성된 순열을 저장하고, 이를 사전 순으로 정렬하기 위한 벡터

void makePermutation(vector<int> combination)
{ // 완성된 조합을 바탕으로 순열을 만들어, 이를 res에 저장하는 함수
    do
    {
        res.push_back(combination);
    } while (next_permutation(combination.begin(), combination.end()));
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    int nums[n]; // 조합에 사용할 배열.
    fill(nums, nums + n, 1);
    for (int i{0}; i < m; i++)
        nums[i] = 0;
    // 조합을 위해, 선택하는 개수인 m만큼 0 선언 / 그 외는 1로 초기화.

    do
    {
        vector<int> combination;
        for (int i{0}; i < n; i++)
            if (nums[i] == 0)
                combination.push_back(nums[i] + i + 1); // 조합 생성

        makePermutation(combination); // 생성된 조합으로 함수 호출
    } while (next_permutation(nums, nums + n));

    sort(res.begin(), res.end()); // res를 사전 순으로 정렬

    for (int i{0}; i < res.size(); i++) // 정렬된 최종 값 출력
    {
        for (int j{0}; j < res[i].size(); j++)
            cout << res[i][j] << " ";
        cout << "\n";
    }
}