BOJ 15663 : N과M (9) - C++
N과M (9)
- N과M 시리즈 중 생각이 좀 필요했던 문제
코드
[ 백트래킹 코드 ]
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int N, M;
int arr[10];
int isused[10];
vector<int> save(10);
void func(int depth){
if(depth == M){
for(int i=0;i<M;i++)
cout << arr[i] <<' ';
cout << '\n';
}else{
/* pre는 지역변수여야함, 전역변수가되면 시작이 다른 수열에도
영향을 준다. */
int pre=-1;
for(int i=0;i<N;i++)
{
if(isused[i]) continue;
if(save[i] == pre) continue;
isused[i] = true;
arr[depth] = save[i];
pre = save[i];
func(depth+1);
isused[i] = false;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for(int i=0;i<N;i++)
cin >> save[i];
sort(save.begin(), save.begin()+N);
func(0);
return 0;
}
- key point!
: 시작이 같은 수열에서 같은 값을 출력하지 않게 조건을 만들어야 한다
(sort
하고 func
실행하기 때문에 바로 이전값을 저장하는 변수를 써야함 prev
)
[ next_permutation 코드 ]
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int N, M;
int arr[10];
vector<int> save(10);
vector<vector<int>> ans;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for(int i=0;i<N;i++)
cin >> save[i];
sort(save.begin(), save.begin()+N);
fill(arr, arr+N, 1);
for(int i=0;i<M;i++) arr[i] = 0;
do{
vector<int> tmp;
for(int i=0;i<N;i++)
if(!arr[i])
tmp.push_back(save[i]);
do{
ans.push_back(tmp);
}while(next_permutation(tmp.begin(), tmp.end()));
}while(next_permutation(arr, arr+N));
sort(ans.begin(), ans.end());
for(int i=0;i<ans.size();i++)
{
bool result = true;
if(i>0){
for(int j=0;j<ans[i].size();j++)
{
if(ans[i-1][j] != ans[i][j]) result = false;
}
}
if(i == 0 or !result){
for(int j=0;j<ans[i].size();j++)
{
cout << ans[i][j] << ' ';
}
cout << '\n';
}
}
return 0;
}
- 로직
1) 2중 do~while()
로 N
개중 M
개를 뽑는 모든 조합
을 구한다
2) ans
를 정렬한뒤, 바로 이전 수열과 같지 않으면 출력한다! (i==0일때 예외처리)
Author And Source
이 문제에 관하여(BOJ 15663 : N과M (9) - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/BOJ-15663-N과M-9-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- N과M 시리즈 중 생각이 좀 필요했던 문제
[ 백트래킹 코드 ]
#include <iostream> #include <algorithm> #include <vector> #include <map> using namespace std; int N, M; int arr[10]; int isused[10]; vector<int> save(10); void func(int depth){ if(depth == M){ for(int i=0;i<M;i++) cout << arr[i] <<' '; cout << '\n'; }else{ /* pre는 지역변수여야함, 전역변수가되면 시작이 다른 수열에도 영향을 준다. */ int pre=-1; for(int i=0;i<N;i++) { if(isused[i]) continue; if(save[i] == pre) continue; isused[i] = true; arr[depth] = save[i]; pre = save[i]; func(depth+1); isused[i] = false; } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> N >> M; for(int i=0;i<N;i++) cin >> save[i]; sort(save.begin(), save.begin()+N); func(0); return 0; }
- key point!
: 시작이 같은 수열에서 같은 값을 출력하지 않게 조건을 만들어야 한다
(sort
하고func
실행하기 때문에 바로 이전값을 저장하는 변수를 써야함prev
)
[ next_permutation 코드 ]
#include <iostream> #include <algorithm> #include <vector> #include <map> using namespace std; int N, M; int arr[10]; vector<int> save(10); vector<vector<int>> ans; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> N >> M; for(int i=0;i<N;i++) cin >> save[i]; sort(save.begin(), save.begin()+N); fill(arr, arr+N, 1); for(int i=0;i<M;i++) arr[i] = 0; do{ vector<int> tmp; for(int i=0;i<N;i++) if(!arr[i]) tmp.push_back(save[i]); do{ ans.push_back(tmp); }while(next_permutation(tmp.begin(), tmp.end())); }while(next_permutation(arr, arr+N)); sort(ans.begin(), ans.end()); for(int i=0;i<ans.size();i++) { bool result = true; if(i>0){ for(int j=0;j<ans[i].size();j++) { if(ans[i-1][j] != ans[i][j]) result = false; } } if(i == 0 or !result){ for(int j=0;j<ans[i].size();j++) { cout << ans[i][j] << ' '; } cout << '\n'; } } return 0; }
- 로직
1) 2중do~while()
로N
개중M
개를 뽑는모든 조합
을 구한다
2)ans
를 정렬한뒤, 바로 이전 수열과 같지 않으면 출력한다! (i==0일때 예외처리)
Author And Source
이 문제에 관하여(BOJ 15663 : N과M (9) - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/BOJ-15663-N과M-9-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)