[백준/C++] 15649번 : N과 M (1)

문제링크

입력 > 5 4

1 2 3 4
1 2 3 5
...

위와 같이 각 자리수마다 크게 n만큼 돌면서 1부터 m까지 중복없이 뽑아서 한줄씩 출력하는 문제입니다.

아이디어

일단 모든 경우의 수를 만들기 위해 제일 마지막 자릿수를 제외한 앞쪽 자리들을 고정시켜놓아야겠다고 생각했다.
위 입력의 경우도 앞쪽 1 2 3은 고정시켜놓고 마지막 자리수와 함께 출력하고 있다.
그래서 다중 for문을 사용하는데 입력이 고정된 값이 아니라서 recursive한 구조로 만들어 for문의 개수를 유동적으로 바뀌게끔 설계할 필요가 있었다.

n=4, m=4인 경우 (1부터 4까지의 자연수 중 4개를 중복없이 선택해서 나열)

for (int i = 1; i <= 4; i++)
	for (int i = 1; i <= 4; i++)
    	for (int i = 1; i <= 4; i++)
        	for (int i = 1; i <= 4; i++)
        		for (int i = 0; i < 4; i++)
					printf("%d ", arr[i]);

n=2, m=2인 경우

for (int i = 1; i <= 2; i++)
	for (int i = 1; i <= 2; i++)
        for (int i = 0; i < 2; i++)
			printf("%d ", arr[i]);

위 코드처럼 바꿔보면 한눈에 어떻게 출력이 되는지 알 수 있을 것이다.
즉 핵심은 for문의 개수를 입력에 따라 바뀌게 하는 것으로 생각할 수 있다.

그리고 visited bool 배열을 선언하여 이미 배열에 저장된 숫자는 출력되지 않게끔 막도록 했다. (아예 출력함수가 있는 for문에 접근하지 않게끔)

느낀점

• cout, cin을 사용했는데 시간초과를 겪었다. 그래서 printf와 scanf를 사용하여 해결했다.
  
  출처

---

제출 코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

using namespace std;

int n, m;

int arr[8] = { 0 }; 
bool visited[8] = { 0 };

void Func(int c)
{
	if (c == m)
	{
		for (int i = 0; i < m; i++)
			printf("%d ", arr[i]);
		puts("");
	} 
	else
	{
		for (int i = 1; i <= n; i++)
		{
			if (!visited[i]) {
				arr[c] = i;
				visited[i] = true;
				Func(c + 1); // 빠져나왔다는건 한 줄 끝났다는 것
				visited[i] = false;
			}
		}
	}
}

int main()
{
	scanf("%d %d", &n, &m);
	Func(0);
}