[백준] 15657 N과 M (8)

November 16, 2021 ( last updated : November 16, 2021 )
백트랙킹 알고리즘

https://github.com/sneakstarberry/

Abstract

[백준] 15657번 N과 M (8)

[백준] 15657번 N과 M (8)

백준 15657번

알고리즘 유형

풀이방법

dfs로 모든 경우의 수를 확인하면서 수열을 출력하는데 수열에 넣을 때 비내림차순을 지키면서 수열에 숫자를 넣습니다. 그리고 기저조건으로 M과 같은 수가 되면 현재 수열을 출력합니다.

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

int N, M;
int arr[9];
vector<int> vec;

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

  for (int i=0; i<N; i++) {
    if(!vec.empty() && vec.back() > arr[i]) continue;
    vec.push_back(arr[i]);
    dfs(cnt+1);
    vec.pop_back();
  }
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> N >> M;
  for (int i=0; i<N; i++) {
    cin >> arr[i];
  }
  sort(arr, arr+N);

  dfs(0);
  return 0;
}

Originally published November 16, 2021
Latest update November 16, 2021

Related posts :

{# #}