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

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

15651번: N과 M (3)

1. 코드

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

int n, m;
string arr;

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++)
	{
		arr.push_back(i + '0');
		solution(position + 1);
		arr.pop_back();
	}
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

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

(실행)

2. 풀이

int n, m;
string arr;

필요한 변수를 선언을 한다. 문자열 arr에 출력하는 값을 저장할 것이다.

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++)
{
	arr.push_back(i + '0');
	solution(position + 1);
	arr.pop_back();
}

만약 그렇지 않다면 문자열 arr에 i + '0'의 값을 push 즉, 문자열 arr 맨 뒤에 i의 값을 문자로 변환하여 추가한다. 그리고 재귀 함수를 호출하는데 종료를 위해 position의 값에서 1을 더한 값을 전달한다. 그리고 재귀 함수에서 탈출하면 문자열 arr의 맨 뒤에 있는 요소를 제거한다. 그렇게 solution의 함수가 재귀 함수로서 계속해서 반복하여 조건에 만족하여 종료가 되면 원하는 값이 도출되어 종료한다.

3. 느낀 점

재귀 함수에 대해 아직은 어색하지만 조금씩 괜찮아지고 있는 것 같다.