[백준] 15650번 : N과 M (2)

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

15650번: N과 M (2)

---

이 문제는 두 가지 방법으로 접근해봤습니다.

<풀이 1>은 오름차순의 조건을 만족하는 배열들만 담아놨다가 출력하는 방법,

<풀이 2>는 모든 배열들을 담아놨다가 출력하는 과정에서 오름차순의 조건을 만족하는 배열만 출력하는 방법

 

 

<풀이 1>

//C++
#include <bits/stdc++.h>
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef long long ll;
using namespace std;

int arr[10];
bool c[10];

void solve(int n, int m, int index, int start)
{
	if (index == m)
	{
		for (int i = 0; i < m; i++)
			cout << arr[i] << ' ';
		cout << '\n';
	}

	for (int i = start; i <= n; i++)
	{

		if (c[i])
			continue;
		c[i] = true;
		arr[index] = i;
		solve(n, m, index + 1, i + 1);
		c[i] = false;
	}
}
int main()
{
	F_I;
	int n, m;
	cin >> n >> m;
	int index = 0;
	int start = 1;
	solve(n, m, index, start);
}

<해설 1>

 

> 고른 수열이 오름차순 이어야 하는 조건이 있다. 다시 말해서, 고른 수열의 원소들이 점점 증가해야 한다는 의미이다.

1 3 2 와 같은 수열은 출력이 되면 안된다. (1 2 3 은 가능하다)

 

> 15649번 :  N과 M (1) 번 문제에서, start라는 변수 하나만 더 추가하면 되는 문제이다. start는 i+1로 설정해야 한다.

index번째에 들어갈 수가 i라면, index+1 번쨰에 들어가야 하는 수는 i보다 커야 하는 수이므로(오름차순)

index+1번째에 들어가야 하는 수의 범위는 i+1~n 이다.

(n이 5이고, m이 2 일때, arr[0]에 2가 들어갔다면, arr[1]에는 3~5사이의 수만 들어갈 수 있다)

---

<풀이 2>

//C++
#include <bits/stdc++.h>
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef long long ll;
using namespace std;

int arr[10];
bool c[10];

void solve(int n,int m,int index)
{
	if (index == m)
	{
		bool flag = true;
		for (int i = 0; i < m-1; i++)
		{
			if (arr[i] > arr[i + 1])
				flag = false;
		}
		if (flag == true)
		{
			for (int i = 0; i < m; i++)
				cout << arr[i] << ' ';
			cout << '\n';
		}
	}

	for (int i = 1; i <= n; i++)
	{

		if (c[i])
			continue;
		c[i] = true;
		arr[index] = i;
		solve(n,m,index+1);
		c[i] = false;
	}
}
int main()
{
	F_I;
	int n, m;
	cin >> n >> m;
	int index = 0;
	solve(n, m, index);
}

<해설 2>

 

> 그냥 15649번 :  N과 M (1) 문제처럼 풀어도 된다. 단, arr을 최종적으로 출력하는 과정에서,

오름차순이 아닌 배열은 걸러내는 작업만 수행하면 된다.

 

> flag 라는 bool 변수를 하나 설정해놓고, 만약 이 배열이 오름차순이 아니라면 flag 를 false로 바꾼다.

 

> 최종적으로 배열을 끝까지 탐색한 이후에, flag가 false라면, 원소들 중에서 오름차순의 규칙을 어긴 원소들이 최소 한번 이상 출현했다는 의미이므로, 그 배열은 출력하지 않는다. flag 가 그대로 true라면, 모든 원소들이 오름차순으로 나열되어있다는 의미이므로, 그 배열은 출력을 허용한다.