[C++] 백준 15663: N과 M (9)

안녕하세요. 오늘 풀어볼 문제는 백준 N과 M (9)입니다.

https://www.acmicpc.net/problem/15663

 

N과 M은 백준에서 아주 유명한 시리즈 문제입니다.

이 시리즈는 모두 N개의 수 중에서 M개를 골라 수열을 출력하는 형식인데요,

그 중에서도 이 아홉 번째 문제는 은근 까다로운 조건을 요구해서 유난히 정답률이 낮습니다.

 

우선 N과 M은 기본적으로 재귀를 통해서 해결하는 문제에요.

 

입력 받은 각 수에 대해서

1. 해당 수를 사용했는지 체크해주고

2. 정답 배열에 해당 수를 넣어주고

3. 다음 깊이에 대해 재귀를 호출하고

4. 해당 수를 사용하지 않는다고 체크해주면 됩니다.

 

Base case는 깊이가 M과 같을 때 정답 배열을 모두 출력해주면 돼요.

 

N과 M (9)에서는 중복된 수가 입력으로 들어올 수 있는 조건이 있습니다.

이 때 발생할 수 있는 문제를 예를 들면 입력으로

2 4 4

가 들어왔을 때 기존처럼 처리하면

2

4

4

와 같은 결과를 얻게 되는 상황이 발생합니다.

 

중복된 두 4는 다른 입력이지만 출력에서는 같은 걸로 취급하죠.

 

해결 방법은 간단합니다.

바로 이번에 사용할 수가 이전에 처리한 수와 같다면 사용하지 않으면 돼요.

 

이미 중복된 수를 거르는 배열이 있지않나라고 생각을 하실 수도 있긴한데요.

그 배열은 서로 다른 깊이에서 중복을 방지하는 역할을 합니다.

지금은 같은 깊이에서 중복을 방지하는 거구요.

그림으로 설명을 해볼게요.

그림을 봐서 더 헷갈릴 수도 있을 거 같기도한데

이해를 잘 하셨을 거라 생각하겠습니다.

 

저는 이전에 사용한 수를 저장하는 변수를 하나 선언해서 매번 비교해줬어요.

비교를 하는 시점은 생각을 해보시면 좋을 거 같습니다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int N, M;
int serial[8];
int result[8];
int chk[8];

void seq(int d) {
	if (M == d) {
		for (int i = 0; i < M; i++)
			cout << result[i] << ' ';
		cout << '\n';

		return;
	}

	int last = 0;
	for (int i = 0; i < N; i++) {
		if (chk[i] != 0 || last == serial[i])
			continue;

		chk[i] = 1;
		result[d] = serial[i];
		last = serial[i];
		seq(d + 1);
		chk[i] = 0;
	}
}

int main() {
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> N >> M;

	for (int i = 0; i < N; i++)
		cin >> serial[i];

	sort(serial, serial + N);

	seq(0);
}