[C/C++] 백준 15651번 N과 M (3)

문제 풀이

이 문제는 '중복 순열'을 이용한 것임. 수를 나열하는 데 같은 수를 사용할 수 있음.

예를 들어 {1,2}라는 숫자 집합이 있다고 할 때, 2개씩 나열하는 중복 순열은 1,1 / 1,2 / 2,2 와 같이 같은 숫자를 사용할 수 있는 것임.

 

코드에 대해 설명하도록 하겠음.

void D(int cnt)
{
	if (cnt==M+1)
	{
		for (int i=1; i<=M; i++)
		{
			cout<<a[i]<<" ";
		}
		cout<<"\n";
	}
	else
	{
		for (int i=1; i<=N; i++)
		{
			a[cnt]=i;
			D(cnt+1);
		}
	}
}

위에 보면 if문에는 종료 조건이 있고, 종료 조건 때는 그 동안 모아 온 재료를 '출력' 또는 '동작'하도록 하는 코드가 있으면 됨.

이 경우에는 M개의 숫자를 출력하는 것이므로 a[i] 배열에 모아 온 숫자를 M개만큼 출력하면 됨.

 

그럼, else 때는 어떤 걸 하냐면 재료를 집어넣는 역할을 함.

		for (int i=1; i<=N; i++)
		{
			a[cnt]=i;
			D(cnt+1);
		}

 

위에서 보면 a[cnt]에 for문으로 '모든 숫자' (중복 순열이므로)를 하나씩 집어 넣고, 이후 재귀 함수를 호출하는 것을 알 수 있음. 재귀 함수 끝나면 이전 cnt에서 for문으로 다른 숫자를 집어 넣고.... 재료 집어 넣기를 반복하는 것임. 하나 끝나면, 그 다음 숫자 그리고 그 다음 숫자.. 그러다 보면 모든 숫자를 집어 넣어 완료하는 게 됨.

 

*참고로 아래 문제에서 시간 초과가 발생하였는 데, 그 이유가 줄바꿈 때 cout<<endl;을 사용해서라는 것을 발견함. cout<<'\n';이 더 빠르다고 함. 이제 endl;은 쓰지 않을 예정.

소스코드

#include <iostream>
#include <vector>
#define MAX 8
using namespace std;

int N;
int M;
int a[MAX];

void D(int cnt)
{
	if (cnt==M+1)
	{
		for (int i=1; i<=M; i++)
		{
			cout<<a[i]<<" ";
		}
		cout<<"\n";
	}
	else
	{
		for (int i=1; i<=N; i++)
		{
			a[cnt]=i;
			D(cnt+1);
		}
	}
}
		
int main() {
	cin>>N>>M;
	D(1);
    return 0;
}