[순열] 백준 : N과 M - 2, 4, 6, 8, 10, 12 (조합)

N과 M (2) : https://www.acmicpc.net/problem/15650

N과 M (4) : https://www.acmicpc.net/problem/15652

N과 M (6) : https://www.acmicpc.net/problem/15655

N과 M (8) : https://www.acmicpc.net/problem/15657

N과 M (10) : https://www.acmicpc.net/problem/15664

N과 M (12) : https://www.acmicpc.net/problem/15666

 

 

2번은 n개의 자연수 중 m개를 고르는 조합(nCm) 문제이고,

4번은 중복 조합을 구하는 문제이다.

6번은 2번과 똑같이 nCm을 구하는 문제인데, n개의 자연수가 크기에 상관없이 주어진다.

8, 10, 12 또한 순열에서 설명했던 것과 동일.

 

 

1, 3, 5, 7, 9, 11 번 문제에서 순열 -> 조합으로 바꾼 문제라고 생각하면 됨.

 

---

 

 

1. 재귀만으로 구현

// 2번 문제

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

using namespace std;

int N, M, number[8] = {1, 2, 3, 4, 5, 6, 7, 8};
vector<int> nums;

void combination(vector<int> nums, int depth)
{
  if (nums.size() == M) // 숫자들을 다 골랐으면(nums가 다 차면), nums를 프린트한다.
  {
    for (auto num : nums)
      cout << num << ' ';
    cout << '\n';
    return;
  }

  for (int i = depth; N > i; i++) 
  // 숫자들을 일일이 체크할 필요 없이, i = depth로 시작하고 재귀에다가 i + 1을 넣어주면
  // 재귀 호출시 인자로 넣어준 depth보다 앞쪽에 위치한 인덱스들은 건너뛰기 때문에 중복 문제를 피할 수 있다.
  {
    nums.push_back(number[i]);
    combination(nums, i + 1);
    nums.pop_back();
  }
}

int main(void)
{
  cin >> N;
  cin >> M;

  combination(nums, 0);
  return 0;
}

 

6번은 2번과 코드가 조합 코드가 완전히 일치하고 처음에 숫자들을 입력받아 정렬하는 코드만 다르기 때문에, 생략한다.

 

nCr = nCr-1 + n-1Cr-1 구현 코드는 건너뛰었다.(순수 재귀만으로 구현하고 싶었다.) 만일 코드를 구현한다면, 함수의 인자에다 n, r을 지정하고 리턴값으로 combination(n, r-1) + combination(n-1, r-1) 이런 형식으로 구현되어야 할 것이다. 기저 조건으로는 r이 0이거나 n이 r과 동일할 때일 것이고.

 

// 10번.

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

using namespace std;

int N, M;
vector<int> nums, number;

void combination(vector<int> nums, int depth)
{
  int prevNum;

  if (nums.size() == M)
  {
    for (auto num : nums)
      cout << num << ' ';
    cout << '\n';
    return;
  }

  for (int i = depth; N > i; i++)
  {

    if (i != depth)
      if (prevNum == number[i])
        continue;

    nums.push_back(number[i]);
    prevNum = number[i];

    combination(nums, i + 1);

    nums.pop_back();
  }
}

int main(void)
{
  int k;

  cin >> N;
  cin >> M;

  for (int i = 0; N > i; i++)
  {
    cin >> k;
    number.push_back(k);
  }

  sort(number.begin(), number.end()); // input으로 들어온 숫자들을 정렬한 후 순열을 구함.

  combination(nums, 0);
  return 0;
}

10번 문제 또한 순열의 9번 문제와 동일하게, 이전 숫자를 저장할 변수를 하나 선정하고 이전 숫자와 현재 숫자를 동일할 시 반복을 건너뛰도록 코드를 작성하면 된다. 다른 코드는 차이가 없다.

 

 

---

 

2. 중복 조합

 

중복 조합은 위의 조합 코드와 비교하여, 딱 한군데가 다르다. 아래는 4번 문제의 코드이다.

 

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

using namespace std;

int N, M, number[8] = {1, 2, 3, 4, 5, 6, 7, 8};
vector<int> nums;

void repComb(vector<int> nums, int depth)
{
  if (nums.size() == M) 
  {
    for (auto num : nums)
      cout << num << ' ';
    cout << '\n';
    return;
  }

  for (int i = depth; N > i; i++)
  {
    nums.push_back(number[i]);
    repComb(nums, i); // 이부분만 다르다. i + 1대신에 i를 넣어준다.
    nums.pop_back();
  }
}

int main(void)
{
  cin >> N;
  cin >> M;

  repComb(nums, 0);
  return 0;
}

 

차이점이라고는, 아규먼트로 i + 1대신에 i를 넣어준 것 밖에 없다. 하지만 이렇게 해줌으로써, 위에서 설명했던 바와 같이 중복 선택을 유도할 수 있다.

8번 코드는 위의 코드와 완전 동일하기 때문에, 생략한다.

12번 코드 또한 이전 숫자를 저장하는 prevNum 관련 코드 외엔 위의 코드와 동일하므로, 생략한다.