N과 M (1)

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

137824

88779

55504

63.373%

문제

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

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

입력

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

출력

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

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

문제 해결 과정

백트랙킹을 활용해 문제를 풀어야 하는 단순예제이다. 다만 이 알고리즘 자체가 DPS 재귀를 이용해야 하기 때문에

로직 자체가 이해하기 쉽진 않다. 나도 여러번 보고, 물어보면서 조금 이해할 수 있었다. 백트랙킹에 관련된 더 다양한 문제들을 풀어봐야 겠다는 생각이 들었다.

#include <iostream>

using namespace std;

int N, M;

int arr[10];
bool visited[10];

//depth는 깊이. (x,y) 에서 y를 담당한다.
void BackTracking(int depth)
{
	//depth가 = M 인경우는 y값이 끝까지 도달했을때 이제 그 한줄을 출력한다.
	if (depth == M)
	{
		for (int i = 0; i < M; i++)
		{
			cout << arr[i] << " ";
		}

		cout << "\n";

		return;
	}
	else
	{
		//백트랙킹 핵심 부분 X의 값을 기준으로 반복을 돌린다
		for (int i = 1; i <= N; i++)
		{
			//사용된 수가 아닐때를 탐색
			if (false == visited[i])
			{
				//방문여부를 갱신하고
				visited[i] = true;

				//현재 선택된 값을 지정
				arr[depth] = i;

				//재귀를 통해서 다음 수를 계산.
				BackTracking(depth + 1);

				//재귀를 빠져나오면 방문여부를 초기화
				visited[i] = false;
			}
		}
	}
}

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

	cin >> N >> M;
	BackTracking(0);
}