[Silver 3] 15657번 N과 M (8)

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

15657번: N과 M (8)

 

이 문제는 DFS를 통한 백트레킹으로 해결할 수 있다.

 

알고리즘은 다음과 같다.

• 입력받은 N개의 숫자를 vector에 삽입하고, 삽입이 끝나면 오름차순으로 정렬한다.
• DFS를 0번째 인덱스, 1번째 자리부터 시작한다.
• num번째 부터 N까지 반복하며 DFS를 수행하면 주어진 조건에 맞게 출력할 수 있다.

 

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int N, M;
int arr[9] = { 0, };
vector<int> graph;

void dfs(int num,int cnt)
{
    if (cnt == M)
    {
        for (int i = 0; i < M; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for (int i = num; i < N; i++)
    {

         arr[cnt] = graph[i];
         dfs(i,cnt + 1);

    }
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        int value;
        cin >> value;
        graph.push_back(value);
    }
    sort(graph.begin(), graph.end());
    dfs(0, 0);
}