[BOJ] 15652번_N과 M (4)_백트래킹 (C++)

[문제]

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

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  *길이가 K인 수열 A가 A1 <= A2 <= ... <= AK-1 <= AK를 만족하면, 비내림차순이라고 한다.

[사용 알고리즘]

백트래킹

[풀이 핵심]

• 이 문제는 N과 M(2)와 N과 M(3)를 섞은 듯한 문제이다.
• 같은 수를 여러 번 골라도 된다는 조건이 존재하므로 visited[] 배열을 사용한 방문 처리를 안해도 된다.
• 비내림차순은 오름차순이 아니다. 비내림차순은 오름차순과 다르게 중복이 허용된다. 따라서 DFS의 인자로 num을 넘겨줄 때 i+1이 아닌 i를 넘겨주면 된다.

[코드]

//boj15652번_N과 M (4)_백트래킹

#include <iostream>

using namespace std;

int arr[9];
int N, M;

void DFS(int v, int num) {
	if (v == M) {
		for (int i = 0; i < M; i++) {
			cout << arr[i] << " ";
		}
		cout << endl;
		return;
	}

	for (int i = num; i <= N; i++) {
		arr[v] = i;
		DFS(v + 1, i);
	}
}

int main() {
	cin >> N >> M;
	DFS(0, 1);

	return 0;
}