[15650] N과 M (2)

---

https://kmyobin.tistory.com/58

[15649] N과 M (1)

이 문제와 유사하다

 

그래서 처음에 풀 때는 기존에 풀었던 15649 코드에 덧붙여서 코드를 완성했다

일단 15649에서 했던 것과 동일하게 A배열을 구한 후, 이 것이 오름차순 배열인지 따져본 다음 오름차순 배열일 때만 출력하게 만들었다

#include <iostream>
#include <algorithm>
using namespace std;

int N, M;
int A[8];
int tmp[8];
bool visited[9];

void arr_copy(int A[], int B[], int size) {
	for (int i = 0; i < size; i++) {
		int temp = A[i];
		B[i] = temp;
		B[i] = A[i];
	}
}

void f(int x) {
	if (x == M) {
		arr_copy(A, tmp, M);
		sort(tmp, tmp + M);
		for (int i = 0; i < M; i++) {
			if (A[i] != tmp[i]) {
				return;
			}
		}
		for (int i = 0; i < M; i++) {
			printf("%d ", A[i]);
		}
		printf("\n");
		return;
	}
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) { // 방문하지 않았다면
			visited[i] = true;
			A[x] = i;
			f(x + 1);
			visited[i] = false; // 다시 바꿔서 다른 곳으로

		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;

	f(0);

}

맞았긴 했는데,, 굳이 배열 하나를 더 추가해서 시간이 더 늘었다

 

그래서 구글링을 통해 다른 사람들의 풀이를 참고했다

이 문제가 15649와 다른 점은 '오름차순'인 수열이어야 한다는 점이다

 

1 2 3 4 (o)

1 3 2 4 (x)

 

그러면 어떻게 해야될까?

dfs로 파고들 때 현재 숫자보다 작은 숫자는 탐색하지 않으면 된다

그렇게 하려면 for문을 약간 수정해줘야 한다

#include <iostream>
#include <algorithm>
using namespace std;

int N, M;
int A[8];
bool visited[9];

void f(int x, int cnt) { // x : A배열에 들어가는 숫자, cnt : A배열의 크기
	if (cnt == M) {
		for (int i = 0; i < M; i++) {
			printf("%d ", A[i]);
		}
		printf("\n");
		return;
	}
	for (int i = x; i <= N; i++) {
		if (!visited[i]) { // 방문하지 않았다면
			visited[i] = true;
			A[cnt] = i;
			f(i + 1, cnt + 1); // 그 다음 수는 전보다 항상 크게 설정
			visited[i] = false; // 다시 바꿔서 다른 곳으로
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;

	f(1,0);
}

이렇게 하면 A배열에 3을 넣은 후 1이나 2를 넣게될 수가 없다

시간도 줄어들었다