BOJ-백준 15650번 N과 M(2) C++

BOJ-백준 15650번 N과 M(2) C++ 문제 풀이 입니다.

링크 : https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

 

 

✅ C++ 정답 코드 입니다. 더보기 클릭!

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

using namespace std;
int n,m;
vector<int>a;
vector<bool>b;

int main() {
  cin >> n>> m;
  for(int i=1; i<=n; i++){
    a.push_back(i);
  }
  for(int i=0; i<n; i++){
    if(i<m)
      b.push_back(true);
    else
      b.push_back(false);
  }

	do{
		for(int i=0; i<a.size(); i++){
			if(b[i])
        cout << a[i] << " ";
		}
		cout << '\n';
	}while(prev_permutation(b.begin(),b.end()));

	return 0;
}

 

 

 

📌 해설

조합을 구하는 문제입니다. C++ algorithm 에 permutation모듈로 조합도 구할 수 있습니다. 다만, 조합을 구할때는 bool 타입의 벡터를 하나 더 사용해서 보조로 사용합니다. 또한 next_permutation이 아닌 prev_permutation으로 이전 순열을 구하는 방식을 선택하였습니다. 4321이라는 순열의 이전 순열은 4312 입니다. 

 

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

using namespace std;
int n,m;
vector<int>a;
vector<bool>b;

1. 필요한 변수와 헤더를 추가합니다. 

a에는 1부터 n까지의 숫자를 담고

bool 타입의 벡터 b는 선택된 숫자의 위치(index)를 기억하도록 합니다. 

 

int main() {
  cin >> n>> m;
  for(int i=1; i<=n; i++){
    a.push_back(i);
  }
  for(int i=0; i<n; i++){
    if(i<m)
      b.push_back(true);
    else
      b.push_back(false);
  }

	do{
		for(int i=0; i<a.size(); i++){
			if(b[i])
        cout << a[i] << " ";
		}
		cout << '\n';
	}while(prev_permutation(b.begin(),b.end()));

	return 0;
}

2. n과 m 을 입력받고 벡터 a와 벡터 b를 초기화 합니다. 

이때, a에는 1부터 n을 순차적으로 삽입하고 

b에는 m만큼 true 나머지는 n 까지 false를 순차적으로 삽입합니다. 

b는 선택된 숫자의 인덱스를 기억하고 있는 벡터이므로 가장 먼저 선택된 숫자는 a[0] (1) 부터 a[m-1] (m)까지의 숫자입니다. 

 

3. do while 문이 실행되면서 b가 prev_permutaion을 돕니다.

아래 표는 n =4, m=2 4C2 를 구하는 과정입니다.  

b = { true, true, false, false } a = { 1, 2, 3, 4 } 1, 2 선택됨	선택된 인덱스는 true, 선택되지 않으면 false입니다.  만약, m=4라면 모두 true이므로 1 2 3 4를 선택한 뒤, prev_permutation을 더 이상구할 수 없기 때문에 종료됩니다.  이 예제에서는 1, 2 2개를 선택합니다.
b = { true, false, true, false } a = { 1, 2, 3, 4 } 1, 3 선택됨	prev_permutation을 도는 b는 처음 초기화 시점에서 내림차순으로 while문을 돕니다. 그래서 { true, false, true, false } 로 인해 1,3이 선택됩니다.
b = { true, false, false, true } a = { 1, 2, 3, 4 } 1, 4 선택됨	{ true, false, false, true } 로 인해1, 4를 선택합니다.

위 과정을 반복하며 조합을 구합니다. 

 

 

 

 

 

::