BaekJoon 15650번: N과 M(2)

간단한 문제지만 BackTracking을 사용하지 않는 경우 생각보다 시간이 오래 걸린다.

 

풀이법

1) 재귀 함수를 이용하여 level에 도달하게 되면 출력하는 형식으로 BackTracking을 구현한다.

2) 방문한 곳을 다시 방문하지 않기 위한 visited 배열과 각 level의 값을 담을 수 있는 arr 배열을

   생각해 낸다면 어렵지 않게 풀 수 있는 문제이다.

3) arr배열의 가장 마지막 원소에 들어가 있는 값을 last으로 두고 이 보다 큰 for문을 돌리면

   문제에서 요구하는 오름차순 수열을 만들 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
int arr[9];
bool check[9];
void backtracking(int level,int last) //level 과 앞 글자를 가지고 온다.
{
	if (m == level)
	{
		for (int i = 0; i < m; i++)
		{
			cout<<arr[i] << " ";
		}
		cout << "\n";
		return;
	}

	for (int i = last; i <= n; i++)//이전 값 보다 커야 하니 i=last
	{
		if (check[i])//방문한 적이 있다면
		{
			continue;
		}
		check[i] = true;
		arr[level] = i;
		backtracking(level + 1, i);
		check[i] = false;
	}
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	backtracking(0,1);//최소 시작 값이 1이므로 last에 1을 넣어준다.
	
}

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest