[boj][c++] 15649 N과M(1), 15650 N과M(2)

15649 N과 M (1)

백트래킹 기본문제. 개어려운데 실버3인가?하는 비교적 낮은 난이도다. (후술하는데 실버3은 개어려운 난이도가 맞다) 사실 이 문제는 반복문 하나와 재귀함수로 구현할 수 있어서 dfs기초라고 생각하고 풀었는데, 재귀함수를 잘 못 다루니까 식을 참조하고도 이해가 너무 어려웠다.
라피신 하면서 dfs를 야매로 이해하고 넘어갔더니 안다고 생각하는 알고리즘에 이런 문제가 생긴다. 기초도 못푸는 그런... 순열을 구하는 문제였는데 dfs 인자를 하나만 받아서 n값과 m값으로 제어하는 식으로 해결했다. 한 줄을 m개만큼 출력해야 하므로 버퍼의 크기는 m값을 기준으로 잡았다. m값 안에 들어가는 수의 조합은 1~n의 자연수이므로 반복문을 1부터 n까지 돌도록 잡았다. 한줄 안에 중복된 수가 있으면 안되기 때문에 이미 사용한 수를 체크하는 배열을 새로 만들었다. 여기에 들어가는게 자연수가 아니었다면 구현이 까다로웠을거 같은데 이런 부분때문에 실버3이라는 등급을 받은 것 같다.

#include	<iostream>
using namespace std;

int n, m;
int arr[9];
bool visit[9];

void dfs(int number)
{
	if (number == m)
	{
		for (int i = 0; i < m; i++)
			cout << arr[i] << " ";
		cout << "\n";
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (visit[i] == false)
		{
			arr[number] = i;
			visit[i] = true;
			dfs(number + 1);
			visit[i] = false;
		}
	}
}

int main()
{
	cin >> n >> m;
	dfs(0);
	return 0;
}

15650 N과 M (2)

앞의 문제와 마찬가지로 백트래킹 기본. 이전 문제는 순열 구하기였는데 이번 문제는 조합 구하기. 앞에선 1 2 / 2 1을 다르다고 생각하고 풀었지만 이번에는 같다고 생각하고 풀어야 해서 조금 더 까다로웠다. 이미 나온 수열이 또 나오면 안되기 때문에 1~n까지 반복할 때 1을 변수로 두고 조절했다. 시작할때 0(버퍼인덱스), 1(사용 가능한 수의 범위)를 보내면 연산된다.

#include	<iostream>
using namespace std;

int n, m;
int arr[9];
bool visit[9];

void dfs(int num, int k)
{
	if (k == m)
	{
		for (int i = 0; i < m; i++)
			cout << arr[i] << " ";
		cout << "\n";
		return;
	}
	for (int i = num; i <= n; i++)
	{
		if (visit[i] == false)
		{
			arr[k] = i;
			visit[i] = true;
			dfs(i+1, k + 1);
			visit[i] = false;
		}
	}
}

int main()
{
	cin >> n >> m;
	dfs(1, 0);
	return 0;
}

백트래킹 어렵다. dfs부터 제대로 공부해야 이정도 난이도 문제를 빨리 풀 수 있을 것 같다.