[SCCC] N과 M(2)_15650번

N과 M(2)_15650번

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n, m;
    vector<int> nums;
    vector<bool> check;
    cin >> n >> m;

    // graph 생성
    for (int i = 1; i <= n; i++)
        nums.push_back(i);

    // check 초기화
    for (int i = 0; i < n; i++) {
        if (i < m)
            check.push_back(true);
        else
            check.push_back(false);
    }

    // next permutation
    do {
        // print
        for (int i = 0; i < nums.size(); i++) { 
            if (check[i])
                cout << nums[i] << " ";
        }
        cout << "\n";
    } while (prev_permutation(check.begin(), check.end()));

    return 0;
}

풀이노트

• 문제의 요지 : nCm 을 구하는 방법
• nCm 을 구할 때 bool 타입의 벡터를 하나 더 사용해서 보조로 이용
• next_permutation 이 아닌 prev_permutation 으로 이전 순열을 구하는 방식을 선택
• vector<bool> check 을 prev_permutation 하면서 do while 문을 돎
  - prev_permutation : 초기화 시점에서 내림차순으로 while 문을 돎
  - T T F F, T F T T, T F F T ... 수열이 만들어짐
• 참고 : https://dlog0518.tistory.com/55?category=929729

• 2^n 하고 싶을 때 pow(2, n) 하면 오차가 발생할 수 있음. pow 는 실수 연산이기 때문
  - 해결책 : 1 << n 을 하면 됨
  - 질문 : 3^n, 4^n 등 2의 제곱이 아닌 경우?