-
백준 1759(암호 만들기)전공/알고리즘 2020. 10. 5. 16:05
딱 봐도 브루트포스이다.
들어가고 안 들어가고, 총 15^2 의 시간복잡도가 소요된다. 따라서 잘 전처리하고, 들어갈때 안 들어갈 때를 구하면 된다.
전처리라고 함은 사전식 배열로 바꾸어 줘야 한다.
그냥 sort로 정렬을 하면 된다.
그러고 나서 재귀로 돌리는데 조건을 잘 짜주자.
#include<iostream> #include<vector> #include<algorithm> using namespace std; int L, C, mo, ja; vector<char> v; vector<char> ans; void solve(int idx, int num) { if (num == L) { if (ja >= 2 && mo >= 1) { for (int i = 0; i < L; i++)cout << ans[i]; cout << '\n'; } return; } if (idx == C) { return; } bool moem = false; if (v[idx] == 'a' || v[idx] == 'e' || v[idx] == 'i' || v[idx] == 'o' || v[idx] == 'u') { moem = true; } if (moem)mo++; else ja++; ans.push_back(v[idx]); solve(idx + 1, num + 1); ans.pop_back(); if (moem)mo--; else ja--; solve(idx + 1, num); } int main() { cin >> L >> C; for (int i = 0; i < C; i++) { char a; cin >> a; v.push_back(a); } sort(v.begin(), v.end()); solve(0, 0); }
'전공 > 알고리즘' 카테고리의 다른 글
백준 1005(ACM Craft) (0) 2020.10.07 백준 2352(반도체 설계) (0) 2020.10.07 백준 13424(비밀 모임) (0) 2020.10.05 백준 15886(내 선물을 받아줘 2) (0) 2020.10.05 백준 2885(초콜릿 식사) (0) 2020.10.04