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

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

15650번: N과 M (2)

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];

필요한 변수들을 선언을 한다.

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이 같다면 출력 예제의 양식에 맞추어 출력을 해주고 반환을 해준다.

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까지의 위치의 인덱스까지 true로 변환시킨다. 그리고 문자열 arr에 해당 i를 문자로 저장을 하고 재귀 함수를 호출하는데 종료를 위해 position에 1을 더한 값을 인자로 전달한다.
 그리고 재귀 함수에서 탈출했다면 다시 1부터 i까지 input의 값을 false를 해주어 해당 i의 값을 사용할 수 있게 해주고 문자열 arr의 마지막 요소를 제거한다.

그리고 이러한 과정을 입력한 값에 대한 조건에 달성할 때까지 반복해주면 문제에서 원하는 답이 나온다.

3. 느낀 점

15649번인 N과 M(1)에서 추가적으로 중복이 되지않게 하는 것이 생각보다 어려웠다. input 배열로 1부터 i까지의 인덱스 값들을 true로 하여 해당 값들을 참조할 수 없게하여 중복을 방지하였다.