백준 15650 N과 M (2)

문제 : https://www.acmicpc.net/problem/15650

 

풀이

N과 M (1)을 풀고 난 후 수정하면 된다.

N과 M (1) : https://hydroponicglass.tistory.com/64

 

1번문제에서 수열을 오름차순으로 출력하라는 조건이 추가되었다.

만약

1 2

1 3

1 4

2 1

2 3

2 4

...

로 출력되면

1 2

1 3

1 4

1 2

2 3

2 4

...

로 바꿔줘야한다.

 

위에서 2 1을 1 2로 바꿔주면 기존에 이미 출력했던 1 2 와 중복된다. 

오름차순으로 정렬하면 중복되는 수가 반드시 존재한다.

그러므로 내림차순으로 출력된다면 그냥 출력하지 않으면 되는 조건문을 추가해주면 된다.

 

---

구현

//c++

#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>

int n, m;
int visited[9];
int seq[9];

void dfs(int value, int idx) {
	//std::cout << value << " " << idx << std::endl;
	if (visited[value] == 1) return;

	seq[idx] = value;

	if (idx == m) {
		for (int i = 1; i <= m; i++) if (seq[i] < seq[i - 1]) return;
		for (int i = 1; i <= m; i++) printf("%d ", seq[i]);
		printf("\n");
		return;
	}

	visited[value] = 1;
	for (int i = 1; i <= n; i++) {
		dfs(i, idx + 1);
	}
	visited[value] = 0;
	return;
}

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