백준 : 15649번 : N과 M(1) (c++)

백준 링크

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	87490	55364	35941	62.446%

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

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

출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1

3 1

예제 출력 1

1
2
3

예제 입력 2

4 2

예제 출력 2

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

코드 풀이

우선 필자의 경우 백트래킹을 사용해본적이 거의 없어 풀이하지 못하였다.

Array를 만들생각을 못하고 재귀 순차적으로 바로바로 출력하려고 해서 실패한 게 가장 큰 원인인 것 같다.

 

코드의 경우 크게 두 가지로 분류 할 수 있다.

1. k, 즉 사용한 숫자의 개수와 M이 같다면 배열에 담긴 값을 출력

2. 백트래킹을 활용한 배열에 값 대입

 

코드

#include <iostream>

using namespace std;

int N, M;
int Array[9];
bool Visit[9];

void Func(int K)
{
	if (K == M)
	{
		for (int i = 0; i < M; ++i)
		{
			cout << Array[i] << ' ';
		}

		cout << '\n';

		return;
	}


	for (int i = 1; i <= N; ++i)
	{
		// 해당 값이 사용 안했어야 가능
		if (!Visit[i])
		{
			Visit[i] = true;
			Array[K] = i;
			Func(K + 1);
			Visit[i] = false;
		}
	}
}


int main()
{
	cin >> N >> M;

	Func(0);

	return 0;
}