[백준/C++]15663, 15664, 15665, 15666번_ N과 M (9~12)

9번, 10번 문제의 차별점은 주어진 수열에서 중복이 있는 수가 있을 수 있다는 것입니다.

문제를 살펴보면 다음과 같습니다.

1. N과 M (9)

두 번째 예시를 보면 알 수 있습니다.

먼저 저는, 이전과 풀던 방식 그대로 + 중복을 제거하는 방법을 추가하는 방법을 이용했습니다.

중복을 점검하는 방법은 c++의 unordered_map 컨테이너를 이용했습니다.

unordered_map<string, int> um;

위의 입력받은 수는 모두 한자리 정수이기 때문에,
출력할 수들을 모두 이어붙인 문자열을 만들고,
결과 출력시에 um의 키 값으로 문자열을 넣고, 이의 값을 1로 만듭니다.

그래서 이후에 똑같은 문자열 (똑같은 수열)이 나오더라도,
해당하는 키의 값이 이미 1로 있기 때문에 중복으로 처리됩니다.

전체 코드는 다음과 같습니다.

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

int n, m;
string str="";
int ch[9]={0, }; // 인덱스 중복 여부 확인 배열
int res[9]={0, }; // 결과 배열
unordered_map<string, int> um; // 수열 중복 여부 확인
vector<int> v;

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

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);

    return 0;
}

---

2. N과 M (10)

9번문제와 거의 비슷하고,
9번에서 비내림차순 조건만 더 추가되었습니다.

이는 DFS함수의 for문안에 있는 if문에서,
"이전 결과에 저장된 값 <= 앞으로 저장될 값" 의 조건을 추가하여 해결하였습니다.

전체 코드는 다음과 같습니다.

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

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

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

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);

    return 0;
}

---

3. N과 M (11)

오히려 9, 10보다 쉽습니다.
처음에 입력받을 때 중복을 미리 제거해주면 앞부분 문제들과 거의 같습니다.
그래서 저는 벡터로 입력받아, 벡터에서 정렬을 한 후 벡터 내부의 중복되는 원소를 제거하는 과정을 먼저 거치고 난 뒤에 DFS를 수행하였습니다.

전체 코드는 다음과 같습니다.

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

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

void DFS(int idx){
  if(idx==m){
    for(int i=0; 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());
    v.erase(unique(v.begin(), v.end()), v.end());
    n=v.size();
    DFS(0);

    return 0;
}

---

4. N과 M (12)

문제는 11에서 오름차순 조건만 추가해주면 됩니다.

전체 코드는 다음과 같습니다.

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

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

void DFS(int idx){
  if(idx==m){
    for(int i=1; i<=m; i++) cout<<res[i]<<" ";
    cout<<"\n";
  }
  else{
    for(int i=0; i<n; i++){
      if(res[idx]<=v[i]){
        res[idx+1]=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());
    v.erase(unique(v.begin(), v.end()), v.end());
    n=v.size();
    DFS(0);

    return 0;
}