[백준] 15665번 N과 M (11) c++

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

15665번: N과 M (11)

 

 

문제접근 및 풀이

기본적인 백트래킹문제이다.

 

고려해야할 사항이 몇가지 있다.

 

1. 중복된 경우를 허용하지 않는다.

-> mul이라는 변수를 사용해서 바로 이전에 선택한 숫자를 저장하여 for문 안에서 mul과 겹친다면 넘어가도록 하여 중복을 없앤다.

 

2. 같은 숫자를 여러번 사용가능하다.

-> 백트래킹시에, for문의 변수 i 를 0부터 시작하여 같은 숫자를 여러번 사용 가능하도록 한다.

 

3. 사전 순으로 증가하는 순서로 출력해야 한다.

-> input 배열을 sort하고 백트래킹시에 0번 인덱스부터 접근한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n,m;
vector<int> input;
vector<int> result;

void bt(int depth){
  if(depth==m){
    for(int i=0; i<result.size(); i++){
      printf("%d ", result[i]);
    }
    printf("\n");
    return ;
  }
  int mul = -1;
  for(int i=0; i<n; i++){
    if(mul == input[i]) continue;
    mul = input[i]; 
    result.push_back(input[i]);
    bt(depth+1);
    result.pop_back();
  }
  return ;
}

int main(){
  cin >> n >> m;
  for(int x,i=0; i<n; i++){
    scanf("%d", &x);
    input.push_back(x);
  }
  sort(input.begin(), input.end());
  bt(0);
  return 0;
}

느낀점

단순히 조합의 경우들을 출력하는 문제라고 생각하고 얉보아 덤볐다가 한대 얻어 맞은 문제이다.

중복을 해결하기가 쉽지 않았다. 처음부터 로직을 한단계 한단계 이해하고 생각해야 했다. 덕분에 기초를 다시 다지는 기회를 가졌다.