자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
c[]
라는 배열에서 숫자를 체크했지만, 오름차순이므로 이번에는 체크할 필요가 없다.이번에는 '선택'하는 관점에서 문제를 풀어보자.
지금까지는 결과 배열에서 0번째 인덱스 부터 M-1번째 인덱스까지 들어올 수 있는 수를 하나씩 조건에 맞도록 '순서대로' 맞춰나갔다면, 이번에는 1 부터 N까지 수에 대해 각각의 수를 '선택하냐', '선택하지않느냐'로 관점을 바꿔보자.
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|
O/X | O/X | O/X | O/X | O/X | O/X | O/X | O/X |
숫자 1부터 '선택 / 선택안함'을 선택하면서 M번 선택할 때 출력하도록 한다. 시간복잡도는 이다.
#include <cstdio>
int n, m, a[9];
void solve(int idx, int num) {
// m개를 만들었으니 출력한다.
if (idx == m) {
for (int i = 0; i < m; ++i) printf("%d ", a[i]);
printf("\n");
return;
}
// 'num'부터 시작해서 숫자를 만든다.
for (int i = num; i <= n; ++i) {
a[idx] = i;
solve(idx + 1, i + 1);
}
}
int main() {
scanf("%d %d", &n, &m);
solve(0, 1);
}
#include <cstdio>
int n, m, a[10];
// num 이라는 수를 포함시킬지 안시킬지 '선택'한다.
void solve(int num, int cnt) {
// m개를 '선택'했으니 출력한다.
if (cnt == m) {
for (int i = 0; i < m; ++i) printf("%d ", a[i]);
printf("\n");
return;
}
if (num > n) return; // 더 이상 선택할 수 있는 수가 없으니 예외처리
a[cnt] = num; // [고정] cnt번째 수로 num을 할당시키고
solve(num + 1, cnt + 1);// [실행] cnt + 1번째 수를 찾으로 num + 1부터 탐색
a[cnt] = 0; // [해제] cnt번째 수를 초기화시켜주고
solve(num + 1, cnt); // [실행] num을 선택하지 않았을 경우에 대해 탐색
}
int main() {
scanf("%d %d", &n, &m);
solve(1, 0);
}