https://www.acmicpc.net/problem/15665
15665번: N과 M (11)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
문제접근 및 풀이
기본적인 백트래킹문제이다.
고려해야할 사항이 몇가지 있다.
1. 중복된 경우를 허용하지 않는다.
-> mul이라는 변수를 사용해서 바로 이전에 선택한 숫자를 저장하여 for문 안에서 mul과 겹친다면 넘어가도록 하여 중복을 없앤다.
2. 같은 숫자를 여러번 사용가능하다.
-> 백트래킹시에, for문의 변수 i 를 0부터 시작하여 같은 숫자를 여러번 사용 가능하도록 한다.
3. 사전 순으로 증가하는 순서로 출력해야 한다.
-> input 배열을 sort하고 백트래킹시에 0번 인덱스부터 접근한다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,m;
vector<int> input;
vector<int> result;
void bt(int depth){
if(depth==m){
for(int i=0; i<result.size(); i++){
printf("%d ", result[i]);
}
printf("\n");
return ;
}
int mul = -1;
for(int i=0; i<n; i++){
if(mul == input[i]) continue;
mul = input[i];
result.push_back(input[i]);
bt(depth+1);
result.pop_back();
}
return ;
}
int main(){
cin >> n >> m;
for(int x,i=0; i<n; i++){
scanf("%d", &x);
input.push_back(x);
}
sort(input.begin(), input.end());
bt(0);
return 0;
}느낀점
단순히 조합의 경우들을 출력하는 문제라고 생각하고 얉보아 덤볐다가 한대 얻어 맞은 문제이다.
중복을 해결하기가 쉽지 않았다. 처음부터 로직을 한단계 한단계 이해하고 생각해야 했다. 덕분에 기초를 다시 다지는 기회를 가졌다.
'알고리즘 문제풀이' 카테고리의 다른 글
| [백준] 2146번 다리 만들기 c++ (0) | 2021.09.05 |
|---|---|
| [백준] 15663 N과 M (9) c++ (0) | 2021.09.04 |
| [백준] 20040번 사이클 게임 c++ (0) | 2021.08.30 |
| [백준] 20046번 Road Reconstruction c++ (0) | 2021.08.30 |
| [백준] 1799번 비숍 c++ (0) | 2021.08.28 |
