알고리즘 문제 풀이/백준 온라인 저지
백준 15666번: N과 M (12) (C++)
Hugxy
2019. 7. 23. 18:02
https://www.acmicpc.net/problem/15666
15666번: N과 M (12)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.
www.acmicpc.net
사용했던 숫자를 여러 번 사용할 수 있다.
따라서 숫자 사용 여부를 관리하는 배열이 필요하지 않다.
수열을 벡터에 쌓고, 원하는 길이만큼 쌓이면 set에 넣고 벡터를 비워주는 것을 반복한다.
set에는 중복되는 원소가 들어갈 수 없다는 것을 활용했다.
#include<iostream> #include<algorithm> #include<set> #include<vector> using namespace std; int m, n, num[8], arr[8], Start; set<vector<int> > st; void func(int k) { if (k == m) { vector<int> v; for (int i = 0; i < m; i++) v.push_back(arr[i]); st.insert(v); v.clear(); return; } if (k == 0) Start = 0; for (int i = Start; i < n; i++) { arr[k] = num[i]; Start = i; func(k + 1); } } int main(void) { cin >> n >> m; for (int i = 0; i < n; i++) cin >> num[i]; sort(num, num + n); func(0); set<vector<int> >::iterator itr; for (itr = st.begin(); itr != st.end(); itr++) { vector<int> tmp = *itr; for (int i = 0; i < tmp.size(); i++) cout << tmp[i] << ' '; cout << '\n'; } return 0; }