백준 알고리즘 15652번: N과 M (4) [C++]

문제출처: www.acmicpc.net/problem/15652

15652번: N과 M (4)

1. 코드

#include <iostream>
#include <string>
using namespace std;

int n, m;
string arr;
bool input[9];

void solution(int position)
{
	if (position == m)
	{
		for (int i = 0; i < m; i++)
			cout << arr[i] << " ";
		cout << "\n";
		return;
	}

	for (int i = 1; i <= n; i++)
	{
		if (!input[i])
		{
			for (int j = 1; j < i; j++)
				input[j] = true;

			arr.push_back(i + '0');

			solution(position + 1);

			for (int j = 1; j < i; j++)
				input[j] = false;

			arr.pop_back();
		}
	}
}

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

(실행)

2. 풀이

int n, m;
string arr;
bool input[9];

필요한 변수들을 선언하는데 여기서 문자열 arr과 bool 배열인 input이 매우 중요하게 쓰이는데 arr같은 경우에는 출력할 요소들을 기억을 하고 input은 출력할 데이터를 선별할 때 씌인다.

cin >> n >> m;
solution(0);

그리고 n과 m을 입력한 뒤 함수 solution에 0을 전달하며 실행한다.

void solution(int position)
{
	if (position == m)
	{
		for (int i = 0; i < m; i++)
			cout << arr[i] << " ";
		cout << "\n";
		return;
	}

그리고 position의 값이 m과 동일하다면 arr의 요소들을 예제 출력의 양식에 맞게 출력 한다.

for (int i = 1; i <= n; i++)
{
	if (!input[i])
	{
		for (int j = 1; j < i; j++)
			input[j] = true;

		arr.push_back(i + '0');

		solution(position + 1);

		for (int j = 1; j < i; j++)
			input[j] = false;

		arr.pop_back();
	}
}

그리고 동일하지 않다면 반복문을 이용하여 input의 값이 false라면 1부터 i - 1의 값까지 input의 해당 인덱스값을 true로 만들어주고 문자열 arr의 마지막에 i + '0'을 추가한다. 즉, i의 문자형태를 문자열인 arr에 저장을 한 뒤 함수 solution posiotion + 1를 전달한다. 그리고 재귀 함수에서 탈출하면 input의 값을 1부터 i - 1까지 false로 초기화시키는데 초기화하는 이유는 1부터 n까지의 수 중 다시 사용할 수가 있기 때문에 이렇게 false로 변환시켜준다. 그리고 arr의 마지막 요소를 합니다. 그리고 이렇게 이 과정을 반복하면 원하는 답의 해답이 나올 것이다.