[boj][c++] 15649 N과 M (1), ..., 15652 N과 M (4)

돌고 도는 재귀 세상

재귀 연습문제로 왕창 풀었다. 이전에 풀고 벨로그에 업로드했던 문제인데 체감상 그때보다 쉽게 푼 것 같다.

15650 N과 M (2)

이전 문제에서 오름차순 정렬 조건만 추가해주면 된다. 다만, 강의와 내 코드에 차이가 있어서 다 정리했다.

강의에서는 오름차순 조건을 걸지 않고 재귀함수 인자에 이전 배열의 값 + 1 을 주어서 반복문을 시작하게 한다. 따라서 bool 자료형 배열이 필요없다.

<내 코드>

#include	<iostream>
using namespace std;

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

void rec(int idx, int n, int m)
{
	if (idx == m)
	{
		for (int i = 0; i < m; i++)
			cout << arr[i] << ' ';
		cout << '\n';
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (check[i]==true)
			continue;
		if (i < arr[idx - 1])
			continue;
		check[i] = true;
		arr[idx] = i;
		rec(idx + 1, n, m);
		check[i] = false;
	}
}

int main()
{
	cin >> n >> m;
	rec(0, n, m);
}

<강의 코드 1>

#include	<iostream>
using namespace std;

int n, m;
int arr[9];

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

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

<강의 코드 2 (추천)>

#include <iostream>
using namespace std;

int a[10];

void go(int index, int selected, int n, int m) 
{
    if (selected == m) 
    {
        for (int i=0; i<m; i++) 
            cout << a[i] << ' ';
        cout << '\n';
        return;
    }
    if (index > n) return;
    a[selected] = index;
    go(index+1, selected+1, n, m);
    a[selected] = 0;
    go(index+1, selected, n, m);
}

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

15651 N과 M (3)

중복 가능하다는 조건때문에 오히려 더 코드가 간결해졌다.

#include	<iostream>
using namespace std;

int n, m;
int arr[8];

void rec(int idx, int n, int m)
{
	if (idx == m)
	{
		for (int i = 0; i < m; i++)
			cout << arr[i] << " ";
		cout << '\n';
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		arr[idx] = i;
		rec(idx + 1, n, m);
	}
}

int main()
{
	cin >> n >> m;
	rec(0, n, m);
}

15652 N과 M (4)

#include	<iostream>
using namespace std;

int arr[9];
int n, m;

void rec(int idx, int n, int m)
{
	if (idx == m)
	{
		for (int i = 0; i < m; i++)
			cout << arr[i] << " ";
		cout << '\n';
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (i < arr[idx - 1])
			continue;
		arr[idx] = i;
		rec(idx + 1, n, m);
	}
}

int main()
{
	cin >> n >> m;
	rec(0, n, m);
}