BOJ_C++_PS
[BOJ/15655번N과M(6)] c++ / backtracking
leebaek
2023. 12. 3. 16:04
문제
주어진 N개의 원소로 이루어진 배열에서 M개의 원소를 골라 수열을 출력하는 문제
-중복되어선 안됨
-수열은 사전순으로 증가하는 순서로 출력되어야 함
생각
백트래킹 사용해서 풀어야겠다 생각함
문제풀이
1.배열을 정렬해줌
2.func(0, 0) - cnt, cur
3.만약 cnt의 개수가 M이면, 수열 출력
4.cur 부터 N까지 사용하지 않은 arr[i]이 나오면
4-1.사용표시 + res[cnt] 에 arr[i] 저장
4-2.func(cnt+1, i) 호출
4-3.사용표시 삭제
코드
#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
int arr[10], res[10];
int isused[10];
void func(int cnt, int cur) {
if ( cnt == M ) {
for ( int i = 0; i < M; i++ )
cout << res[i] << ' ';
cout << '\n';
return;
}
for ( int i = cur; i < N; i++ ) {
if ( !isused[i] ) {
isused[i] = 1;
res[cnt] = arr[i];
func(cnt+1, i);
isused[i] = 0;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for ( int i = 0; i < N; i++ ) cin >> arr[i];
sort(arr, arr+N);
func(0, 0);
}