백준 15651번: N과 M (3) (C++)

문제는 아래와 같다.

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

15651번: N과 M (3)

 

이번에는 숫자를 중복해서 사용할 수 있다.

 

이전까지는 숫자의 중복을 제한하기 위해서 isused배열을 사용했다. 숫자가 arr배열을 이루는 데에 사용되고 있다면 true 값을 가지도록 하고 그렇지 않은 경우 false 값을 가지도록 하였다.

 

이번에는 이것이 필요하지 않다.

 

또한 문제를 풀이하는 과정에 있어서, 배열을 인자로 넘기지 않고 전역변수로 사용해도 좋다.

 

k값도 마찬가지이다. k값을 인자로 넘기지 않으려면, 재귀에 들어가기 전에 k값을 증가시키고,

 

재귀에서 탈출한 이후에는 k값을 줄여줘야한다.

 

또한 k를 0부터 시작할지 1부터 시작할지도 편한 데로 선택하면 되겠다.

 

나 같은 경우에는 k를 0부터 시작하는 경우, ~까지는 수열이 만들어져 있다는 의미로 보았다.

 

1부터 시작하는 경우에는, 이번에는 ~번째 자리의 숫자를 채울 차례다라는 의미로 생각하면 되겠다.

 

당연하게도 의미가 다르기 때문에 base condition의 조건도 달라져야 한다.

 

전자의 경우 k==m인 경우가 기저 조건이고, 후자의 경우 k > m 인 경우를 기저 조건이라고 보면 된다.

 

 

//전역변수 활용
#include<iostream>
using namespace std;
int arr[8], N, M; //1 indexed
//int k = 0;
void func(int k) {
	if (k > M) {
		for (int i = 1; i <= M; i++)
			cout << arr[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = 1; i <= N; i++) {
		arr[k] = i;
		func(k + 1);
	}
}
int main(void) {
	cin >> N >> M;
	func(1); 
	return 0;
}