#15652: N과 M(4)

백준 15652번: N과 M (4)

문제:

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

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

입력:

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

풀이:

• 이 문제는 #15649: N과 M(1)과 풀이법이 거의 동일하다. 따라서 #15649: N과 M(1) 풀이법을 한번 읽어보기를 권한다. 요약하자면 재귀함수를 이용하여 배열을 오른쪽으로 한칸씩 이동하는데 이때 백트래킹을 이용하여 끝에 다다른 경우 정답을 출력한 뒤 돌아와서 다시 숫자를 넣어준다.

  🔍 백트래킹이란 정답을 찾던 도중 막히면 다시 뒤로 돌아와서 정답을 찾는 방법을 말한다. 퇴각검색이라고도 불린다. 한 칸 뒤로가서 다시 다른 길로 가보고 이 길이 아니면 다시 뒤로 돌아오고를 반복한다. 이 문제의 경우에는 정답을 찾던 도중 막혔다기보다는 정답을 찾았으니 또 다른 정답을 출력하기 위해 한칸 뒤로 “퇴각”한 뒤 다시 앞으로 다른 숫자를 넣는다고 생각하면 된다.

• 이 문제가 #15649: N과 M(1)과 다른점은 같은 수가 중복이 가능하다는 점과 자신보다 크거나 작은 수를 뒤에 두어야 된다는 점이다. 우선, 같은 수를 이용해도 되므로 현재 숫자가 사용중인지 확일할 필요가 없다. 마지막으로 자신보다 작은 수가 뒤에 올 경우를 제거해주는 if문을 추가 해주면 된다.

코드:

#include <iostream>

using namespace std;

int n, m, answer[8]={};

void brute_force(int index){
	//끝에 도착하면 정답 출력 후 인덱스 한칸 "퇴각"
	if(index == m){
		for(int i = 0; i < m; i++) cout<<answer[i]<<" ";
		cout<<'\n';
		return;
	}
	//1부터 n까지 모든 수를 넣기 위한 for문
	for(int i = 1; i <= n; i++){
		//자신보다 작은 수가 뒤에 올려고 하는 경우 무시하고 다음 수로 넘어간다
		if(i<answer[index-1]) continue;
		answer[index] = i; //알맞는 값 저장
		brute_force(index+1); //다음 칸으로 넘어간다
		answer[index] = 0; //"퇴각"하였으니 0으로 초기화
	}
}
int main(){
	//입력
	cin >> n >> m;
	//재귀함수 시작
	brute_force(0);
}