[SCCC] N과 M_15649번

N과 M_15647번

코드

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

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

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

    // next permutation
    do
    {
        for (int i = 0; i < m; i++)
            cout << nums[i] << " ";
        cout << "\n";
        reverse(nums.begin() + m, nums.end());
    } while (next_permutation(nums.begin(), nums.end()));

    return 0;
}

풀이노트

• 문제 풀이 방법

  • 수열(✔️)
  • dfs 이용

• 문제의 요지 : nPm 을 구하는 방법

• do while 을 이용해서 모든 수열을 출력 -> nPn 인 경우가 됨

• 예) n=4, m=1 인 경우

  • 1 2 3 4, 1 2 4 3, 1 3 2 4 ... 수열이 만들어짐
  • reverse(nums.begin() + m, nums.end()) 가 있으면
    • 1 2 3 4 -> 1 4 3 2(reverse) -> 2 1 3 4(next_permutation) 가 만들어짐
    • 1 다음에 4 가 나오면 시작이 1 인 배열이 모두 완성되었다고 판단하기 때문에 시작이 2 인 배열부터 만들 수 있음

• 참고 : https://dlog0518.tistory.com/54?category=929729