알고리즘 :: 백준 :: Bruteforce :: 15649 :: N과 M (1)

Embedded June·2021년 2월 10일
0

알고리즘::백준

목록 보기
61/109

문제

문제링크

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

문제접근

  • <algorithm>헤더의 next_permutation() 함수를 쓰면 간단하게 풀 수 있는 문제지만, 만일 STL을 사용할 수 없는 경우라면 이 문제를 어떻게 풀 수 있을지 생각해보자.
  • N과 M의 범위가 8까지로 매우 작기 때문에 bruteforce를 사용해보자. 재귀적인 관점에서 순서를 만들어가보자.
  • 재귀적 bruteforce의 핵심알고리즘은 고정, 실행 그리고 해제다.
  • 재귀를 돌면서 결과 배열의 idx번 위치에 1부터 8까지의 숫자를 넣고 다음 재귀를 돌리고 다시 빼는 과정을 반복한다.

코드

#include <iostream>

int n, m, c[9], a[9];

void solve(int idx) {
	// m개를 선택했다면, 결과를 출력한다.
	if (idx == m) {
		for (int i = 0; i < m; ++i) printf("%d ", a[i]);
		printf("\n");
		return;
	}
    	// 1부터 n까지의 수를 '고정', '실행', '해제'한다.
	for (int i = 1; i <= n; ++i) {
		if (c[i]) continue;
		a[idx] = i;
		c[i] = 1;
		solve(idx + 1);
		c[i] = 0;
		a[idx] = 0;
	}
}

int main() {
	scanf("%d %d", &n, &m);
	solve(0);
}

결과

profile
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.

0개의 댓글