[백준 C++] 15650번 : N과 M(2)

1. 문제

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

15650번: N과 M (2)

 

2. 알고리즘 분류

• 백트래킹

 

3. 소스 코드

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

int N, M;
vector<int> nums;

// 수열을 구하는 함수(DFS 이용)
// lv : 현재 뽑은 숫자의 갯수, num : 이전에 뽑았던 수
void permutation(int lv, int num) {

	// M개 까지 숫자를 뽑았을 때, 끝내기
	if (lv == M) {
    	
        // 뽑은 숫자들을 출력
		for (int i = 0; i < nums.size(); i++)
			cout << nums[i] << " ";
            
		cout << '\n';

		return;
	}

	// 이전의 뽑았던 수보다 큰 수 부터 차례대로 수 뽑기(오름차순)
	for (int i = num + 1; i <= N; i++) {
		nums.push_back(i);
		permutation(lv + 1, i);
		nums.pop_back();
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
    // 고른 수열은 오름차순
	cin >> N >> M;

	// 수열을 구하는 함수
	permutation(0, 0);

	return 0;
}

 

4.  상세 설명

1. 첫번째 숫자를 뽑을 때, 1 ~ N 까지 숫자를 하나씩 뽑기
2. 이전에 뽑았던 수 보다 큰 수만 뽑기
3. 뽑은 수가 M개라면, 뽑는 것을 중단하고 뽑은 수들을 출력
4. 이전에 뽑은 수를 하나하나씩 되돌리고, 1 ~ 3번을 반복

4.1) 예시

1. 첫번째 숫자를 뽑을 때, 1 ~ N 까지 숫자를 하나씩 뽑기
	nums = 1

2. 이전에 뽑았던 수 보다 큰 수만 뽑기
	nums = 1, 2 -> 1, 2, 3 -> ... -> 1, 2, 3, 4, 5

3. 뽑은 수가 M개라면, 뽑는 것을 중단하고 뽑은 수들을 출력
	5개 뽑았으면, "1 2 3 4 5"로 출력

4. 이전에 뽑은 수를 하나하나씩 되돌리고, 1 ~ 3번을 반복
	nums = 1, 2, 3, 4, 5 -> 1, 2, 3, 4 -> 1, 2, 3, 4, 6
    "1 2 3 4 6" 출력
    
    nums = 1, 2, 3, 4, 6 -> 1, 2, 3, 4 -> 1, 2, 3 -> 1, 2, 3, 5 -> 1, 2, 3, 5, 6
    "1 2 3 5 6" 출력

 

5.  문법

5.1) 1 ~ N까지의 자연수 중에서 중복 없이 M개를 고른 순열(오름차순)

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

int N, M;
vector<int> nums;

void permutation(int lv, int num) {
	if (lv == M) {
		for (int i = 0; i < nums.size(); i++)
			cout << nums[i] << " ";
            
		cout << '\n';
		return;
	}

	for (int i = num + 1; i <= N; i++) {
		nums.push_back(i);
		permutation(lv + 1, i);
		nums.pop_back();
	}
}

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

	permutation(0, 0);

	return 0;
}