[백준 15650/c++] N과 M (2)

22. 08 .02 코드 수정 - 타 풀이 참고

오름차순 순열의 조건을 새 함수로 설정하지 말고, 백트래킹 함수에 인자를 하나 추가하여

백트래킹 내 재귀 시에 항상 자신의 값보다 더 큰 수를 갖도록 하여 오름차순이 되도록 구현,

더 큰 수 이므로 중복을 체크하기 위한 isused 조건도 빼주어 더욱 간결한 코드로 바꿀 수 있다

---

22. 08. 01

백트래킹 문제에 오름차순 순열이라는 조건이 걸린 문제이다

해당 수가 이전에 사용된 수들 보다 큰지를 체크 하여 맞을 시 참을 리턴하는 함수를 만들어 (0은 항상 참)

백트래킹의 조건 중 하나로 집어 넣어서 풀었다

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

15650번: N과 M (2)

<-- 수정 후 -->

#include <bits/stdc++.h>
using namespace std;

int n, m;
int ar[10];

bool check(int s, int t){
	if (s == 0)
	{
		return true;
	}
	for (int i = 0; i < s; i++)
	{
		if (ar[i] - t > 0)
		{
			return false;
		}
	}
	return true;
}

void bt(int k, int num){
	if (k == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << ar[i] << " ";
		}
		cout << "\n";
		return;
	}
	for (int i = num; i <= n; i++)
	{
		ar[k] = i;
		bt(k + 1, i + 1);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	
	cin >> n >> m;
	bt(0, 1);
	
	return 0;
}

---

<-- 수정 전 -->

#include <bits/stdc++.h>
using namespace std;

int n, m;
int ar[10];
bool isused[10];

bool check(int s, int t){
	if (s == 0)
	{
		return true;
	}
	for (int i = 0; i < s; i++)
	{
		if (ar[i] - t > 0)
		{
			return false;
		}
	}
	return true;
}

void bt(int k){
	if (k == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << ar[i] << " ";
		}
		cout << "\n";
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (!isused[i] && check(k, i))
		{
			ar[k] = i;
			isused[i] = true;
			bt(k + 1);
			isused[i] = false;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	
	cin >> n >> m;
	bt(0);
	
	return 0;
}