백준 [실버3] 15654 N과 M (5)

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

 

접근 방식

< 재귀를 통해서 이중 for문을 구현하는 방법 >

https://hyon123.tistory.com/67

백준 [실버3] 15649 N과 M (1)

 

 

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열의 값을 2번째로 주어진 배열의 인덱스 값으로 사용하면 이 문제는 간단하게 풀린다

 

한번 사용한 숫자는 다시 사용하면 안되기 때문에 isused라는 숫자 사용 여부를

포함한 bool 배열을 추가해 for 문 재귀를 돌기 전에 미리 확인했다

 

소스코드

 

#include <bits/stdc++.h>

using namespace std;
int N,M;
int input[8];
int arr[8];
bool isused[8];

void recur(int cur)
{
    if(cur == M)
    {
        for(int i = 0; i < M; i++)
        {
            cout << input[arr[i]-1] << " ";
        }
        cout << "\n";

        return;
    }

    for(int i = 1; i <= N; i++)
    {
        if(isused[i])
        {
            continue;
        }

        isused[i] = true;
        arr[cur] = i;
        recur(cur+1);
        isused[i] = false;
    }
}

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

    cin >> N >> M;

    for(int i = 0; i < N; i++)
    {
        cin >> input[i];
    }

    sort(input,input+N);

    recur(0);

    return 0;
}