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

1) 문제   

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

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

2) 입력   

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

3) 출력   

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

4) 해결방법   

전체적인 코드 구조는 백준 15649번의 N과 M 두번째 문제와 비슷하다. 아직 두번째 문제를 풀지 않았다면, 그 문제부터 푸는 것을 추천한다. 

2021.04.30 - [백준 문제풀이/Backtracking] - [c++] 백준 15650: N과 M(2)

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

하지만 두번째 문제와의 차이점은 숫자를 중복으로 사용 가능하다는 것이다. 그렇다면 두번째 문제의 코드에서 if (!visited[i])의 조건문을 삭제하여 숫자를 중복으로 쓸 수 있게 해준다. 또한, 시작 인자를 전달할 때, 이전보다 1 큰 숫자를 전달하는 것이 아니라, 이전과 같은 숫자에서 중복으로 쓸 수 있도록 dfs(i, cnt + 1) 로 구현해야한다. 

5) 전체코드   

#include<iostream>
using namespace std;

int n, m;
int arr[9] = { 0, }; //선정된 숫자를 저장할 배열
bool visited[9] = { 0, }; //선정된 숫자인지 판단할 수 있는 배열

void dfs(int num, int cnt) {
	if (cnt == m) {
		for (int i = 0; i < m; i++) { //m개의 숫자가 선정되었다면 
			cout << arr[i] << ' '; //선정된 숫자들 출력
		}
		cout << "\n";
		return;
	}
	for (int i = num; i <= n; i++) { //이전과 같은 숫자부터 시작
			visited[i] = true; //i를 선정
			arr[cnt] = i; //arr에 추가
			dfs(i, cnt + 1);
			visited[i] = false; //그 전의 성공단계
	}
}

int main() {
	cin >> n >> m;
	dfs(1, 0);
}

 

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

15652번: N과 M (4)