백준 15649

https://www.acmicpc.net/problem/15649
브루트 포스 문제

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

문제풀이

어떤 숫자를 썼는지 알려주는 배열 c(check)와 답 배열 a(answer)을 사용한다. go 함수의 가장 첫번째 조건문은 총 M개의 숫자를 받았는지 체크한다.
index[0]부터 index[m-1]번째까지 어떤 값이 들어있기 때문이다.
go함수의 for문의 i가 1부터 n까지인 이유는(0부터 n-1까지가 아니고) 밑의 표와 같다.

0부터		1부터
0 1		1 2
0 2		1 3
1 0	->	2 1
1 2		2 3
2 0		3 1

풀이 상상

재귀함수 go를 구현해 첫번째 if문에 index와 m을 비교해서 꽉 차면 답을 출력하게 한다.
두번째 for문에서 1부터 n까지 반복한다.
a[index]에는 i를 넣어주고 c[i]에 true를 해줌으로서 c[1,2,3…,n의 수가 존재함]을 알 수 있다.
그러므로 for문 첫번째 줄에 if(c[i]) continue 추가. go재귀함수를 호출하고 나서는 다시 c[i]를 false로 바꾸어준다.
브루트포스 알고리즘은 처음 봤을때 이해하기가 너무 어려워서 오랜 시간동안 프로그램 진행모습 표를 그려보면서 이해했습니다.
제 논리대로 코딩하는건 그냥 하면 되지만(안되면 바꿔보고..물론 이 방법은 안좋은 방법입니다) 실제로 프로그램이 돌아가는 모습은 복잡한 것 같다는 생각이 듭니다. 재귀함수 어려워

소스코드

#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);
}