[백준 C++] 15652번 : N과 M(4)

1. 문제

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

15652번: N과 M (4)

2. 알고리즘 분류

• 백트래킹

 

3. 소스 코드

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

int N, M;
vector<int> nums;

// 순열을 구하는 함수
// 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; 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);

	cin >> N >> M;

	// 순열 구하는 함수
    // 1부터 N까지 자연수 중에서 M개를 고른 수열
    // 중복 가능, 비내림차순
	permutation(0, 1);

	return 0;
}

 

4.  상세 설명

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

4.1) 예시

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

2. 이전에 뽑았던 수 보다 크거나 같은 수만 뽑기
	nums = 1, 1 -> 1, 1, 1 -> ... -> 1, 1, 1, 1, 1

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

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

 

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; 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);

	cin >> N >> M;

	permutation(0, 1);

	return 0;
}