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

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

15649번: N과 M (1)

문제

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

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

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

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

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

---

풀이

Algorithm

• 문제 이해하기

이 문제는 간단해 보이지만 다소 생각이 조금 필요한 문제이다.

우선, 숫자 N개 중에 M개를 골라야 한다는 점에서, for문이 M번 반복되어야 하고,

중복이 없이 선택한다는 점에서, 순차적으로 하나씩 숫자를 고른다고 가정할 때 이미 앞에서 골랐던 숫자를 저장하는 list가 필요함을 알 수가 있다.

또 여기에서 숫자를 고를 때마다 골랐던 숫자를 저장하는 list가 갱신 되어야 하고, for문에 계속 반복되어야 하므로 재귀함수가 유용함을 생각해내야 한다!

여기까지 생각하면 이제 문제는 다 푼거나 마찬가지이다!

 

• 함수 설명

1. k번째 숫자를 고른다고 생각해보자,

2. 우선 k번째 숫자의 후보는 1부터 N까지가 될 수 있다. 하지만 이미 앞에서 고른 숫자가 아니어야 한다. 이에 대해 for문을 돌리면서 하나씩 검사해본다.

3. 후보였던 숫자가 앞에서 골랐던 숫자가 아니라면, list에 해당 수를 추가해준다. 즉 후보가 k번째 숫자로 선택된 것이다.

4. 만약 k가 M보다 작아 다음 숫자를 골라야 한다면, 다시 갱신된 list와 len을 넣은 이 함수를 호출하여 다음 숫자를 고르는 작업을 수행한다.

4. 하지만 이때 만약, k번째가 마지막이라면 더 고를 숫자가 없으므로 앞에서 골랐던 숫자 모두를 출력해준다!

 

• 변수 설명

int list[8] : 앞에서 고른 숫자들을 담고 있는 함수 / 아무것도 없는 리스트였다가 숫자를 하나씩 고를 때마다 갱신된다.

int len : 이미 고른 숫자가 몇 개인지, 즉 list의 length가 몇인지! / 숫자를 하나씩 고를 때마다 1씩 증가한다.

bool flag : 숫자를 한개씩 고를 때마다 그 숫자가 선택될 수 있는 수인지 판별해주는 변수이다. / 이미 골랐었던 숫자들을 검사해 중복되는 애가 있는 지 알려준다!

 

Code

#include <iostream>
using namespace std;

void choice(int* _list, int _len, int _N, int _M) {
	for (int i = 1; i <= _N; i++) { // 여기에서 i란, 선택 후보가 되는 수 입니다!
		bool flag = false; // 현재 선택됐었던 애들(_list에 있는 애들) 중에 i와 같은 수가 있는지?
		for (int j = 0; j < _len; j++) { // _list를 모두 탐색해보면서
			if (_list[j] == i) { // i와 같은 애가 있으면
				flag = true;
				break; // 더 볼 필요도 없으니까 바로 if문 빠져 나오기
			}
		}
		if (!flag) { // i가 한번도 선택되지 않았던 애라면!
			_list[_len] = i; // i를 선택된 애들 리스트에 넣어주고,
			if (_len + 1 == _M) { // 그런데, 이때 M개를 모두 골랐다면,(즉 마지막 숫자를 고른 거라면)
				for (int i = 0; i < _len + 1; i++) // 이제까지 고른 애들을 모두 출력해준 다음,
					cout << _list[i] << ' ';
				cout << endl;
			}
			else if (_len + 1 < _M) // 아직 숫자를 더 골라야 한다면,
				choice(_list, _len + 1, _N, _M); // 그 다음 숫자를 고르는 작업을 수행!
		}
	}
}

int main() {
	int N, M, list[8], len = 0;
	cin >> N >> M;
	choice(list, len, N, M);
	return 0;
}