백준 15650,15651

N과 M (2), N과 M(3)

브루트 포스 문제

N과 M을 입력받고, 1부터 N까지, M개의 숫자의 수열을 중복없이 오름차순으로 출력하는 것이다.

N과 M (1) 번을 풀었다면 아주 조금의 코드 수정만 있다면 쉽게 풀 수 있는 문제.
풀지 않았다면 위의 포스팅을 먼저 보고 오시길 바랍니다.

N과 M(2) 문제풀이

go 재귀함수에서 i의 시작점을 1부터 시작하면 모든 index에서 1부터 시작한다.
이 점을 잘 생각해보면 그 전 index에서 사용한 수의 다음부터 저장하면 된다는 것을 알 수 있다.
즉, 반복문의 시작을 이렇게 바꾸면 된다.

int i = a[index-1]+1;

소스

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
bool c[10]; int a[10];
void go(int index, int n, int m) {
	if (index == m)
	{
		for (int i = 0; i < m; i++)
			cout << a[i] << ' ';
		cout << '\n';
		return;
	}
	
	for (int i = a[index-1]+1; i <= n; i++)
	{
		if (c[i])
			continue;
		c[i] = true;
		a[index] = i;
		go(index + 1, n, m);
		c[i] = false;
	}
}
int main() {
	int n,m;
	cin >> n>>m;
	go(0, n, m);
}

N과 M(3) 문제풀이

중복 없이란 말만 빠졌으므로 이전 코드에서 중복을 제거해줬던 check관련 코드 세줄을 제거해 주면 됩니다.

소스

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
bool c[10]; int a[10];
void go(int index, int n, int m) {
	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])
		//	continue;
		//c[i] = true;
		a[index] = i;
		go(index + 1, n, m);
		//c[i] = false;
	}
}
int main() {
	int n,m;
	cin >> n>>m;
	go(0, n, m);
}