[BOJ]15649번: N과 M (1)(c++)

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

15649번: N과 M (1)

 

방법 1 : BFS

#include <iostream>
 
using namespace std;
 
const int MAX = 8;
int visited[MAX + 1];
char output[MAX * 2 + 1];
 
void perm(int N, int M, int depth)
{
    // depth가 목표 길이에 도달하면 출력
    if (depth == M)
    {
        cout << output << '\n';
        return;
    }
 
    // 1~N까지의 숫자 중에서 M 자릿수 숫자 조합 만들기
    for (int i = 1; i <= N; i++)
    {
        // 이전에 선택하지 않은 숫자중에서 다음 숫자 선택
        if (!visited[i])
        {
            visited[i] = true;
            output[depth * 2] = i + '0';
            output[depth * 2 + 1] = ' ';
            perm(N, M, depth + 1);
            visited[i] = false;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int N, M;
    cin >> N >> M;
 
    perm(N, M, 0);
 
    return 0;
}

 

방법 2: 라이브러리 사용

#include <iostream>
#include <algorithm>
#include <string>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int N, M;
    cin >> N >> M;
    
    string nCm;
    
    for (int i = 1; i <= N; i++)
    {
        nCm.push_back((char)i + '0');
    }
 
    int tmp = 0;
    do 
    {
        int res = stoi(nCm.substr(0, M));
 
        if (res > tmp)
        {
            for (int i = 0; i < M; i++)
            {
                cout << nCm[i] << " ";
            }
            cout << '\n';
            tmp = res;
        }
    } while (next_permutation(nCm.begin(), nCm.end()));
 
    return 0;
}

 

방법 2는 그냥 할수 있어서 해본것이다. 

이문제에서는 방법1이 더 좋은 풀이. 

결과를 입력하는 배열을 int배열보다 char배열로 선언하는 게 더 빠르고 깔끔하다.