[C++][백준 15649번] N과 M (1) ⭐

15649번: N과 M (1)

 

📄 문제

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

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

 

📝 풀이

• 순열을 구하는 문제입니다.
• N개의 자연수 중 M개를 선택하여 모든 가능한 순서대로 배열하여 만들어야 합니다.
  • ch는 인덱스 번호에 삽입한 자연수입니다.
  • used는 해당 인덱스 번호를 사용하였는지 검사하기 위해 사용합니다.
• {1, 2}와 {2, 1}은 서로 다른 순열입니다. 이는 조합과 다릅니다.
• Permutations 함수에서 s가 M(선택할 개수)와 같다면 해당 함수는 종료됩니다.
  • s는 현재 선택한 개수를 뜻합니다.
• 0부터 N까지 반복하여 used[i]가 false인 경우에만 ch에 저장한 후, s + 1을 하여 다음 DFS로 넘어갑니다.

// Online C++ compiler to run C++ program online
#include <iostream>

int N, M;

int ch[8];
int used[8];

void Permutations(int s)
{
	if (s == M)
	{
		for (int i = 0; i < M; ++i)
			printf("%d ", ch[i] + 1);
		printf("\n");
	}
	else
	{
		for (int i = 0; i < N; ++i)
			if (!used[i])
			{
				used[i] = true;
				ch[s] = i;
				Permutations(s + 1);
				used[i] = false;
			}
	}
}

int main() 
{
    scanf("%d %d", &N, &M);
    
    Permutations(0);

    return 0;
}