[15652] N과 M (4)

---

이번 조건은 특이하다

같은 수를 여러 번 골라도 되고, 고른 수열이 비내림차순이어야 한다

 

비내림차순 : 각각의 원소가 바로 앞에 있는 원소보다 크거나 같아야 함

ex) 1 2 2. 2 2 3, 4 5 6

 

https://kmyobin.tistory.com/58?category=1084833 

[15649] N과 M (1)

전에 만들어놓았던 백트래킹 과정이 정말 도움이 많이 되었다

저기서 (2,1)이 출력되지 않으려면 어떻게 해야될까..!

바로 전에 담았던 숫자를 기억하는 변수 하나를 만들어 줘야 하겠지

전역변수로 before를 선언했다

 

그 다음 백트래킹을 진행하던 for문을 조금 바꿔준다

	for (int i = 1; i <= N; i++) {
		if (i >= before) {
			A[x] = i;
			before = i;
			f(x + 1);
			before = i;
		}
	}

백트래킹을 진행하기 직전에 before에 담았던 수를 넣어준다

 

그리고 f(x+1) 이후에 다시 before를 선언해주는 이유는 백트래킹 함수를 완전히 다 돈 후 다시 빠져나왔을 때 before 값을 for문에 맞게 다시 설정해주는 것이다

다른 백트래킹 함수에 있는 before을 쓰면 안되기 때문임

 

말로 하니까 좀 이상한데, 밑에 줄 before = i; 가 없어지면

입력 : 4 2

이렇게 된다

 

다섯번째 줄에서 before = 4가 되는데, return 후 다시 돌아왔을 때도 before가 4이기 때문에 모든 for문을 지나치게 돼서 저렇게 출력이 되는 것이다

그래서 before을 다시 설정한 것!

 

 

그래서 완성된 코드는 아래와 같다

#include <iostream>
using namespace std;

int N, M;
int A[8];
int before;

void f(int x) {
	if (x == M) {
		for (int i = 0; i < M; i++) {
			printf("%d ", A[i]);
		}
		printf("\n");
		return;
	}
	for (int i = 1; i <= N; i++) {
		if (i >= before) {
			A[x] = i;
			before = A[x];
			f(x + 1);
			before = A[x];
		}
	}
}

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

	cin >> N >> M;

	f(0);

}