BOJ 15650 N과 M (2)

15650번: N과 M (2)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

문제 풀이

이 문제는 백트래킹을 사용하여 문제를 풀었습니다. 

백트래킹이란 ? 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘입니다.

위와 같은 방식으로 한 배열와 특정한 수가 쓰였는지에 대한 배열을 선언해 주고 점점 단계를 거치면서 조건에 맞게 배열을 출력해주자. N과 M (1) 과 거의 유사한 문제지만 오름차순으로 출력해야 한다. 이부분만 추가 된 문제이다.

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
int n, m;
int arr[10];
int isused[10];
void func(int k)
{
	if (k == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = 1; i <= n; i++)
	{
		if (!isused[i]&&i>=arr[k-1]||k==0)
        // 현재 수 i 와 바로 이전 수 arr[k-1] 비교해서 현재수가 이전수보다 커야함(오름차순)
        //k==0 조건은 유효한 인덱스를 참조록하는 조건문 추가. 
		{
			arr[k] = i;
			isused[i] = 1;
			func(k + 1);
			isused[i] = 0;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	func(0);
}

 

글 내용 중에 틀린 것이 있거나 궁금한 것이 있다면 댓글 남겨주세요! 봐주셔서 감사합니다!