[백 트래킹] BOJ 15666 N과 M (12)

 

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

15666번: N과 M (12)

 

문제 해결 알고리즘

 

전형적인 dfs를 활용한 백트래킹 문제. 비내림차순일 때 출력해주는 것만 유의하면 된다.

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int N, M; 
int arr[9];
vector<int> v;
map<int,int> numberCnt;

bool flag(){
  for(int i=0;i<M-1;i++){
    if(arr[i] > arr[i+1]) return false;
  }
  return true;
}

void dfs(int n){

  if(n == M){
    if(flag()){
      for(int i=0;i<M;i++){
        cout << arr[i] << ' ';
      }
      cout << '\n';
    }
    return;
  }

  for(int j=0;j<v.size();j++){
    arr[n] = v[j];
    dfs(n+1);
  }
}

int main(){
  cin >> N >> M;
  
  for(int i=0;i<N;i++){
     int num; cin >> num;

     if(!numberCnt.count(num)){
       numberCnt[num] = 1;
       v.push_back(num);
     }
     else numberCnt[num]++;

    
  }

  sort(v.begin(), v.end());
  
  dfs(0);
}

 

메모

if문 작성할 때 순서에 유의해야한다.

if(n == M){
    if(flag()){
      for(int i=0;i<M;i++){
        cout << arr[i] << ' ';
      }
      cout << '\n';
    }
    return;
  }

if(n == M && flag()){
      for(int i=0;i<M;i++){
        cout << arr[i] << ' ';
      }
      cout << '\n';
    }
    return;

 

두 개의 코드는 차이는 엄청난 차이였다..