[백준/c++] 15649번: N과 M (1)
1857 단어 Bruth ForceBruth Force
[문제]
[풀이]
[재귀함수로 풀수 있는 브루트포스 문제 종류]
- 순서와 관련된 문제 -> N가지 중에서 M개를 뽑을 때, 순서가 중요한 문제
- 시간복잡도 : N!
- 선택과 관련된 문제 -> N가지 중에서 M개를 뽑을 때, 일부를 선택하거나, 선택하지 않음.
- 시간복잡도 : 2^N (2개의 선택이 총 N가지 있는거니까)
[풀이]
- 이 문제에서는 N개중 M개를 고르는 문제이고, 순서가 다르면 다른 수열이므로 순서와 관련된 브루트포스 문제이다.
- 수열에서의 위치에 따라 올 수 있는 조건이 달라지므로 '위치'는 함수의 인자로 들어가야함.
- 위치에따라 조건이 달라진다는 말은?
-> 예를들어, 1번자리에 4가 왔다면 2번자리에는 4가 올 수 없고, 2번자리에 3이 왔다면 3번자리에는 3,4,가 올수없음. (이렇게 이전 위치에 따라 다음 위치에 올 수 있는 수의 조건이 달라짐)
-
check[i]: i를 사용했으면 true, 안했으면 false
-
arr[] : 수열 저장하는 배열
-
func(index,n,m)함수의 역할 : index번째의 수를 결정.
-
이 문제의 시간복잡도 : N(N-1)...*1=N!
[코드]
//15649. N과 M (1)
#include <iostream>
using namespace std;
bool check[10];
int arr[10];
void func(int index,int n,int m){
if(index>m){
// 수열 출력 부분
for(int i=1; i<=m; i++){
cout<<arr[i]<<" ";
}
//한번의 출력이 끝나면 줄바꿈 해주기
cout<<"\n";
return;
}
for(int i=1;i<=n; i++){
if(check[i])
continue;
check[i]=true;
arr[index]=i;
func(index+1,n,m);
check[i]=false;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin>>n>>m;
func(1,n,m);
}
Author And Source
이 문제에 관하여([백준/c++] 15649번: N과 M (1)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@somyeong0623/백준c-15649번-N과-M-1저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)