[백준] 15666 N과 M (12)

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

https://github.com/sneakstarberry/

Abstract

[백준] 15666번 N과 M (12)

[백준] 15666번 N과 M (12)

백준 15666번

알고리즘 유형

풀이방법

dfs로 모든 경우의 수를 확인하면서 수열을 출력하는데 수열에 넣을 때 이전에 넣어던 값을 다시 넣지 않도록 해주면서 넣어줍니다. 그리고 비내림차순으로 값을 넣어줍니다. 기저 조건은 M과 같을 때 수열을 출력하도록 합니다.

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

int N, M;
vector<int> nums;
vector<int> vec;
bool is_visited[9] = {false,};
void dfs(int cnt) {
  if(cnt == M) {
    for(int i=0;i<M;i++) {
      cout << vec[i] << ' ';
    }
    cout << '\n';
    return;
  }
  int prev_num = -1;
  for (int i=0; i<N; i++) {
    if ( prev_num == nums[i]) continue;
    if ( !vec.empty() && vec.back() > nums[i]) continue;
    is_visited[i] = true;
    vec.push_back(nums[i]);
    prev_num = nums[i];
    dfs(cnt+1);
    vec.pop_back();
    is_visited[i] = false;
  }

}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> N >> M;
  for (int i=0; i<N; i++) {
    int tmp;
    
    cin >> tmp;
    nums.push_back(tmp);
  }
  sort(nums.begin(), nums.end());

  dfs(0);
  return 0;
}

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

Related posts :

{# #}