[백준/C++]15654, 15655, 15656, 15657번_ N과 M (5~8)

N과 M 문제 이어 5~8까지 풀이를 함께 올리겠습니다.

5~8은 1~4의 조금 응용 버전이고, 핵심은 같아서 풀이만 올리겠습니다.

1. N과 M (5)

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

int n, m;
int ch[10001]={0, }; // 중복 여부 확인 배열
int res[9]={0, }; // 결과 배열
vector<int> v;

void DFS(int idx){
  if(idx==m+1){
    for(int i=1; i<=m; i++) cout<<res[i]<<" ";
    cout<<"\n";
  }
  else{
    for(int i=0; i<n; i++){
      if(!ch[v[i]]){
        ch[v[i]]=1;
        res[idx]=v[i];
        DFS(idx+1);
        ch[v[i]]=0;
      }
    }
  }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m;
    for(int i=0; i<n; i++){
      int tmp; cin>>tmp;
      v.push_back(tmp);
    }
    sort(v.begin(), v.end());
    DFS(1);

    return 0;
}

제 풀이는 다음과 같습니다.
따로 정렬부분을 신경쓰지 않기위해 먼저 입력을 받고 정렬을 먼저 해주었습니다.
나머지 부분은 거의 같습니다.

---

2. N과 M (6)

풀이 1) 시간복잡도 O(n^m)

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

vector<int> v;
int res[9]={0, };
int ch[10001]={0, };
int n, m, s=0;

void DFS(int cnt){
  if(cnt==m+1){
    for(int i=1; i<=m; i++){
      cout<<res[i]<<" ";
    }
    cout<<"\n";
  }
  else{
    for(int i=0; i<n; i++){
      if(!ch[v[i]] && res[cnt-1]<v[i]){
        res[cnt]=v[i];
        ch[v[i]]=1;
        DFS(cnt+1);
        ch[v[i]]=0;
      }
    }
  }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m;
    int tmp;
    for(int i=1; i<=n; i++){
      cin>>tmp; v.push_back(tmp);
    }
    sort(v.begin(), v.end());
    DFS(1);
    return 0;
}

풀이 2) 시간복잡도 O(2^m)

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

int n, m;
int ch[10001]={0, }; // 중복 여부 확인 배열
int res[9]={0, }; // 결과 배열
vector<int> v;

void DFS(int idx, int cnt){
  if(cnt==m){
    for(int i=0; i<n; i++){
      if(ch[i]) cout<<v[i]<<" ";
    }
    cout<<"\n";
  }
  else if(idx>=n) return;
  else{
    ch[idx]=1;
    DFS(idx+1, cnt+1);
    ch[idx]=0;
    DFS(idx+1, cnt);
  }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m;
    for(int i=0; i<n; i++){
      int tmp; cin>>tmp;
      v.push_back(tmp);
    }
    sort(v.begin(), v.end());
    DFS(0, 0);

    return 0;
}

---

3. N과 M (7)

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

int n, m;
int ch[10001]={0, }; // 중복 여부 확인 배열
int res[9]={0, }; // 결과 배열
vector<int> v;

void DFS(int idx){
  if(idx==m+1){
    for(int i=1; i<=m; i++){
      cout<<res[i]<<" ";
    }
    cout<<"\n";
  }
  else{
    for(int i=0; i<n; i++){
      res[idx]=v[i];
      DFS(idx+1);
    }
  }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m;
    for(int i=0; i<n; i++){
      int tmp; cin>>tmp;
      v.push_back(tmp);
    }
    sort(v.begin(), v.end());
    DFS(1);

    return 0;
}

---

4. N과 M (8)

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

int n, m;
int ch[10001]={0, }; // 중복 여부 확인 배열
int res[9]={0, }; // 결과 배열
vector<int> v;

void DFS(int idx){
  if(idx==m+1){
    for(int i=1; i<=m; i++){
      cout<<res[i]<<" ";
    }
    cout<<"\n";
  }
  else{
    for(int i=0; i<n; i++){
      if(res[idx-1]<=v[i]){
        res[idx]=v[i];
        DFS(idx+1);
      }
    }
  }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m;
    for(int i=0; i<n; i++){
      int tmp; cin>>tmp;
      v.push_back(tmp);
    }
    sort(v.begin(), v.end());
    DFS(1);

    return 0;
}