글 읽기 - 맞긴 했는데 이 방법이 맞는지는 모르겠습니다.

didqhtmd 3년 전 0

일단 맞았다고 나오는데 이 방법이 맞는지 모르겠습니다.

제 알고리즘은 n차 for문을 구현을 목표로 해서 해당 부분을 재귀문으로 만들었는데요,

출력할 배열을 따로 만들어두어서 재귀문으로 들어가기 전에 해당 배열에 삽입하고 재귀문 호출은 남은 for문 갯수를 감소 시켰습니다.

백트래킹 부분은 isIn()불린 함수로 출력할 배열에 해당 수가 있는지를 확인하게끔 했고요.

근데 이렇게 구현하는게 맞나요?

일반적으로는 어떻게 구현하나요?

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

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

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

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

*/
// 1부터 N 까지 수 중에 중복없이 M 개를 고른 수열
#include <iostream>
using namespace std;

// 재귀문
void backTrack(int forRemain, int numMax, int printArray[], int forMax); 

// 순열 배열 출력 함수
void printCombo(int arr[], int printsize); 

// 스킵 조건: arr내부에 obj가 있는지 확인. (중복 확인)
bool isIn(int arr[], int size, int obj); 


int main() {
	int N, M;
	cin >> N >> M;
	int numbers[8] = {0};

	backTrack(M, N, numbers, M);
	return 0;
}

void backTrack(int forRemain, int numMax, int printArray[], int forMax) {
	int reversedIndex = forMax - forRemain;	// forRemain == 1 일때가 첫번째 자리.

	if (forRemain == 1) {
		for (int i = 1; i <= numMax; i++) {
			if (isIn(printArray, forMax, i))
				continue;
			printArray[reversedIndex] = i;
			printCombo(printArray, forMax);				
			printArray[reversedIndex] = 0;

		}

		return;
	}
	else {
		for (int i = 1; i <= numMax; i++) {
			if (isIn(printArray, forMax, i))
				continue;

			printArray[reversedIndex] = i;
			backTrack(forRemain - 1, numMax, printArray, forMax);
			printArray[reversedIndex] = 0;
		}
	}


}

void printCombo(int arr[], int printsize) {
	for (int i = 0; i < printsize; i++)
		printf("%d ", arr[i]);
	printf("\n");

}

bool isIn(int arr[], int size, int obj); {
	for (int i = 0; i < size; i++)
		if (arr[i] == obj)
			return true;
	return false;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

맞긴 했는데 이 방법이 맞는지는 모르겠습니다.

didqhtmd 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말