728x90
반응형
이 문제는 dfs이다.
이 문제는 N과 M(6)과 N과 M(9)와 연관된 문제이다.
중복되는 수열을 여러번 출력하면 안되며,
수열은 중복된 수로 나열되어있을 수 있다.
포인트는
'N과 M(6) + 재귀 시 중복된 수가 있는지 확인'
이다.
N과 M(6)은 조합문제이다.
조합 코드는 두 가지가 있는데,
void combination(int target, int index, vector<int> realVector, vector<int> numVector){
if(target == 0){
sort(numVector.begin(), numVector.end());
combinationVector.push_back(numVector);
return;
}
if(index == realVector.size()){
return;
}
numVector.push_back(realVector[index]);
combination(target - 1, index + 1, realVector, numVector);
numVector.pop_back();
combination(target, index + 1, realVector, numVector);
}
하나는 index로 반복해서 굳이 for문과 방문여부를 체크하지 않아도 되고,
void combination(int target, int index, vector<int> realNumVector,vector<int> numVector){
if(target == 0){
for(int i = 0; i < numVector.size(); i++){
cout << numVector[i] << " ";
}
cout << "\n";
return;
}
for(int i = index; i < realNumVector.size(); i++){
if(selected[i]) continue;
numVector.push_back(realNumVector[i]);
selected[i] = true;
combination(target - 1, i, realNumVector, numVector);
selected[i] = false;
numVector.pop_back();
}
}
두번째는 for문과 방문여부를 체크해야한다.
N과 M(9)처럼 재귀 시 중복된 수가 있는지 확인하면 된다.
나는 for문으로 이루어진 조합코드를 활용했다.
//백준 N과 M (10)
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
int selected[8] = {false};
void combination(int target, int index, vector<int> realNumVector, vector<int> numVector){
if(target == 0){
for(int i = 0; i < numVector.size(); i++){
cout << numVector[i] << " ";
}
cout << "\n";
return;
}
int beforeNum = -1;
for(int i = index; i < realNumVector.size(); i++){
if(selected[i] || beforeNum == realNumVector[i]) continue;
selected[i] = true;
beforeNum = realNumVector[i];
numVector.push_back(realNumVector[i]);
combination(target - 1, i, realNumVector, numVector);
numVector.pop_back();
selected[i] = false;
}
}
int main(void){
int count, target, num;
cin >> count >> target;
vector<int> realNumVector, numVector;
for(int i = 0; i < count; i++){
cin >> num;
realNumVector.push_back(num);
}
sort(realNumVector.begin(), realNumVector.end());
combination(target, 0, realNumVector, numVector);
}
https://github.com/jeongdaeun98/algorithm/blob/master/2020/20102902.cpp
jeongdaeun98/algorithm
백준, 프로그래머스. Contribute to jeongdaeun98/algorithm development by creating an account on GitHub.
github.com
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 연산자 끼워넣기 & 연산자 끼워넣기 2 (0) | 2020.10.30 |
---|---|
[algorithm] 백준 - 이모티콘 (0) | 2020.10.30 |
[algorithm] 백준 - N과 M(9) (0) | 2020.10.30 |
[algorithm] 백준 - ABCDE (0) | 2020.10.29 |
[algorithm] 백준 - N과 M (8) (0) | 2020.10.29 |