백준, BOJ, 1759번, 암호만들기 : C++ [CPP] ★★★★

//첫번째 풀이 2021.12.05

//두번째 풀이 2022.02.08

어렵다기보다는..

조건이 많은 문제였다.

 

https://www.acmicpc.net/problem/1759

 

---

 

#맞은 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int L, C;

vector <char> vec;

bool isUsed[15];


//L,C는 글로벌, 백트래킹함수 -> 차례대로 고름
void func(int cnt, string s) {

    //L개 골랐다면 출력할지 정함 -> 자음 2개 모음 1개
    if (cnt == L) {
        int consonant = 0;
        int vowel = 0;
        for (int i = 0; i < L; i++) {
            if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') {
                vowel++;
                continue;
            }
            else {
                consonant++;
            }
        }
        if (consonant >= 2 && vowel >= 1) {
            cout << s << '\n';
        }
        return;
    }

    //선택하는 부분
    for (int i = 0; i < C; i++) {
        //중복선택 x
        if (!isUsed[i]) {

            //비어있으면 그냥 지나감
            if (!s.empty()) {
                //비어있지 않다면 증가하는 순서로 뽑아야함 -> 가장 마지막보다 조금 더 큰 알파벳만 골라야함
                if (s.back() > vec[i])continue;
            }

            //선택, 카운트, 복원
            isUsed[i] = true;
            s.push_back(vec[i]);
            func(cnt + 1, s);
            s.pop_back();
            isUsed[i] = false;
        }
    }


}

int main() {
    cin >> L >> C;
    for (int i = 0; i < C; i++) {
        char c;
        cin >> c;
        vec.push_back(c);
    }
    //ascending sorting
    sort(vec.begin(), vec.end());


    //시작, 빈 문자열
    func(0, "");





    return 0;
}

 

 

어렵지 않았다.

사실 백트래킹 갈것도 없었다.

차례대로 뽑는대신..

문자열의 가장 마지막보다 큰 것만 뽑으면 되었다.

아무튼 뭐 그렇다.

 

---

 

#두 번째 풀이

#include <bits/stdc++.h>

using namespace std;

int L, C;
vector<char> vec;

int vowel, consonant; // 모음, 자음;

bool check[15];

void func(int cnt, string s, int idx){
    if(cnt == L && vowel >= 1 && consonant >= 2){
        cout << s << '\n';
    }
    
    for(int i = 0; i<C; i++){
        if(check[i]) continue;
        if(i<idx) continue;
        
        check[i] = true;
        if(vec[i] == 'a' || vec[i] == 'e' || vec[i] == 'i' || vec[i] == 'o' || vec[i] == 'u'){
            vowel++;
            func(cnt+1, s + vec[i], i);
            vowel--;
            check[i] = false;
        }else{
            consonant++;
            func(cnt+1, s + vec[i], i);
            consonant--;
            check[i] = false;
        }
        
        
    }
    
}


int main(){
    cin >> L >> C;
    
    for(int i = 0; i<C; i++){
        char ch;
        cin >> ch;
        vec.push_back(ch);
    }
    sort(vec.begin(), vec.end());
    
    func(0,"", 0);
    
    
    return 0;
}

 

 

이번엔 이 아이디어를 떠올리지 못했다.

다만 더 빠르게 풀었다.

-> 다음엔 증가하는 순서를 뽑을 때 idx로 받아도 좋지만 저렇게 받아도 좋을 것 같다.

 

저기서 이제 뒤에 것이 앞에 것보다 더 증가하게 뽑으려면 2가지가 있다.

현재 상태를 알거나

지난 번의 상태를 저장하거나

위에가 현재 상태를 접근해서

아래가 지난 번의 기록했던 idx로 아무튼 생각하고 넘어갈만한 문제다.

//비어있으면 그냥 지나감
            if (!s.empty()) {
                //비어있지 않다면 증가하는 순서로 뽑아야함 -> 가장 마지막보다 조금 더 큰 알파벳만 골라야함
                if (s.back() > vec[i])continue;
            }

 

func(cnt+1, s + vec[i], i);