링크
https://www.acmicpc.net/problem/15654
문제
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.
- N개의 자연수 중에서 M개를 고른 수열
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
4 5 2예제 출력 1
2
4
5예제 입력 2
4 2
9 8 7 1예제 출력 2
1 7
1 8
1 9
7 1
7 8
7 9
8 1
8 7
8 9
9 1
9 7
9 8예제 입력 3
4 4
1231 1232 1233 1234예제 출력 3
1231 1232 1233 1234
1231 1232 1234 1233
1231 1233 1232 1234
1231 1233 1234 1232
1231 1234 1232 1233
1231 1234 1233 1232
1232 1231 1233 1234
1232 1231 1234 1233
1232 1233 1231 1234
1232 1233 1234 1231
1232 1234 1231 1233
1232 1234 1233 1231
1233 1231 1232 1234
1233 1231 1234 1232
1233 1232 1231 1234
1233 1232 1234 1231
1233 1234 1231 1232
1233 1234 1232 1231
1234 1231 1232 1233
1234 1231 1233 1232
1234 1232 1231 1233
1234 1232 1233 1231
1234 1233 1231 1232
1234 1233 1232 1231아이디어 스케치
구해야하는 수열의 조건을 살펴보면,
N개의 자연수 중에서 M개를 고르고,
중복되는 수열을 여러 번 출력하면 안되며, 사전 순으로 증가하는 순서로 출력해야 한다.
위 조건을 만족하는 수열을 구하기 위해서 백트래킹 알고리즘을 이용하였다.
구현 로직
-
사전 순으로 증가하는 순서로 출력하기 위해 입력 받은 N개의 수를 퀵 정렬을 이용하여 오름차순으로 정렬
-
하나의 수열에 같은 숫자를 사용하는 것을 방지하기 위해 check 배열 사용
=> 현재 만들고 있는 수열에서 사용된 숫자는 check[사용중인 숫자]를 1로 설정하므로써 if조건문에 들어갈 수 없게 함 -
조건을 만족하는 길이가 M인 수열을 구한 경우에는 결과를 출력
전체 코드
#include <stdio.h>
#include <stdlib.h>
int N, M;
int result[1000]; // 완성된 하나의 수열을 저장하는 배열
int check[10001]; // 중복체크를 위한 배열
int list[8]; // 입력으로 주어지는 수를 저장하는 배열
// 퀵정렬을 위한 compare 함수(오름차순 정렬)
int compare(const void* f, const void* s)
{
if (*(int*)f > *(int*)s)
return 1;
else if (*(int*)f < *(int*)s)
return -1;
else
return 0;
}
// 조건에 맞는 순열을 찾아 출력하는 함수
void Sequence(int depth)
{
int i;
if (depth == M) // 조건을 만족하는 길이가 M인 수열을 구한 경우
{
for (i = 0; i < M; i++) {
printf("%d ", result[i]); // 결과 출력
}
printf("\n");
}
else
{
for (i = 0; i < N; i++)
{
if (check[list[i]] == 0) // 같은 숫자를 사용하는 것을 방지
{
result[depth] = list[i]; // 현재 자리수에 list[i]값을 저장
check[list[i]] = 1; // list[i]를 사용중으로 체크
Sequence(depth + 1); // 다음 자리수를 탐색
check[list[i]] = 0; // 재귀 호출이 끝나면 0으로 초기화
}
}
}
}
int main(void)
{
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++)
scanf("%d", &list[i]);
//수열을 사전 순으로 증가하는 순서로 출력하기 위해 오름차순 정렬 수행
qsort(list, N, sizeof(int), compare);
Sequence(0); // depth는 0부터 시작
return 0;
}제출 결과
IT Velog