백준: Gold5⑤ - 1747, 1753, 1759

</br> 계속 계속
</br>

1747: 소수&팰린드롬

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

n보다 큰 소수이면서 팰린드롬인 수 찾기

bool isPalin(string s){
    int sz = s.size();
    for(int i = 0; i < sz/2; i++){
        if( s[i] != s[sz-1-i] ) return false;
    }
    return true;
}

// in main()
    primes[0] = 1;
    primes[1] = 1;
    for(int i = 2; i <= 1003001; i++){
        if( primes[i] == 0 ){
            if( i >= n && isPalin(to_string(i)) ){
                cout << i << endl;
                return 0;
            }
            for(int j = 2; j*i <= 1003001; j++){
                primes[j*i] = 1;
            }
        }
    }

N이 1000000까지인데, 얘로 만들 수 있는 가장 큰 소수 팰린드롬은 1003001이라서 이걸 리미트로 걸었다.
에라토스테네스의 체로 소수가 아닌 것들은 제외하면서 확인하고, 발견하면 바로 종료한다.

</br>

1753: 최단경로

https://www.acmcpc.net/problem/1753

방향 그래프에서 최단 경로 구하기

    priority_queue< P, vector<P>, greater<P> > pq;
    pq.push(mp(0, start));
    dist[start] = 0;
    while( pq.size() ){
        int vw = pq.top().first;
        int vi = pq.top().second;
        pq.pop();
        if( vw > dist[vi] ) continue;
        for(int i = 0; i < graph[vi].size(); i++){
            int ni = graph[vi][i].first;
            int cost = vw + graph[vi][i].second;
            if( cost < dist[ni] ){
                dist[ni] = cost;
                pq.push(mp(dist[ni], ni));
            }
        }
    }
    for(int i = 1; i <= v; i++){
        if( dist[i] == INT_MAX ) cout << "INF" << endl;
        else cout << dist[i] << endl;
    }

처음에 배열로 했는데 메모리 초과 나서 인접 리스트로 바꿔줬다…
정점 개수가 20000까지고 시간 제한이 1초라서 플로이드 워셜은 안 되고, 다익스트라 알고리즘을 사용하면 된다.
우선순위 큐로, 현재 정점에서 갈 수 있는 곳들을 푸시하면 가장 가까운 게 탑에 있게 된다.
만약 거리를 업데이트할 수 있다면 업데이트한다.
</br>

1759: 암호 만들기

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

최소 모음 1개 자음 2개를 포함한 정렬된 문자열 만들기

void func(int d, int pn, int chn, int now){
    if( d == l ){
        if( pn >= 1 && chn >= 2 ) cout << s << '\n';
        return;
    }
    for(int i = now+1; i < c; i++){
        s.append(1, ch[i]);
        if( parent[ch[i]-'a'] ) func(d+1, pn+1, chn, i);
        else func(d+1, pn, chn+1, i);
        s.erase(s.end()-1);
    }
}

// in main()
    sort(ch.begin(), ch.end());

    parent[0] = 1;
    parent['e'-'a'] = 1;
    parent['i'-'a'] = 1;
    parent['o'-'a'] = 1;
    parent['u'-'a'] = 1;
    func(0, 0, 0, -1);

다 해보면 된다. 일단 사전순으로 만들기 위해 입력 받은 걸 정렬한다. 그리고 모음을 표시한다.
func()은 d: 현재 만든 문자열의 크기, pn: 모음의 수, chn: 자음의 수, now: 현재까지 인덱스로 중복된 문자를 사용하지 않게 한다.
</br>

---

오늘은 잠이 오네
</br>