#15650: N과 M(2)

#15650: N과 M(2)

백준 15649번: N과 M (2)

문제:

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력:

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

풀이:

풀이 방법은 N과 M(1)과 동일하지만 조건문 하나가 추가 되어서 자세한 풀이는 N과 M(1)의 풀이를 참고하면 될 것 같다. 고른 수열은 오름 차순이라는 조건만 추가 되였는데 출력 예시를 보면 중복 된 값이 안나오도록 원하는 문제였다. “중복 없이”의 기준이 두 문제에서 달라진 것 같다. 이 문제를 풀기 위해 추가 된 두번째 for loop에 첫번째 조건문 조건문은 현재의 i 값이 전 숫자 보다 작으면 넘겨서 큰 숫자만 출력 되도록 고쳤다. 출력 된 값이 전부 전의 인덱스 보다 큰 숫자가 오기 때문에 이렇게 생각하여 풀었다.

코드:

#include <iostream>

using namespace std;

int n, m, c[9], a[9];

void brute_force(int index){
	if(index == m){
		for(int i = 0; i < m; i++){
			cout << a[i] << " ";
		} 
		cout << "\n";
		return;
	}
	for(int i = 1; i <= n; i++){
		if(c[i] || i < a[index-1]) continue;
		a[index] = i;
		c[i] = 1;
		brute_force(index+1);
		c[i] = 0;
		a[index] = 0;
	}
}

int main(void){
	cin >> n >> m;
	brute_force(0);
	
}