BOJ 6588 골드바흐의 추측 / BOJ 1916 최소비용 구하기 / BOJ 1406 에디터

백준 BOJ 6588번 : 골드바흐의 추측

Solved.ac 난이도 : Silver I

알고리즘 분류 : 에라토스테네스의 체

 

1,000,000 이하의 짝수가 주어질 때, 합이 그 짝수와 같은 두 소수를 구하거나, 또는 그런 소수 쌍이 존재하지 않음을 구하는 문제입니다.

하나의 입력에 테스트케이스가 최대 10만개까지 주어질 수 있으므로, 소수 판별을 미리 해놓고 결과값만 가져오는 방식으로 해결해야 시간 초과를 받지 않고 통과할 수 있습니다.

따라서 에라토스테네스의 체를 활용하여 문제를 풀어주어야 합니다.

 

 

#include<bits/stdc++.h>
#define MAX 1000001
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    bool is_prime[MAX] = {};
    for(int i=2; i<MAX; i++) is_prime[i] = true;
    for(int i=2; i*i<MAX; i++)
        for(int j=2; i*j<MAX; j++) is_prime[i*j] = false;

    vector<int> prime;
    for(int i=2; i<MAX; i++)
        if(is_prime[i]) prime.push_back(i);

    while(true) {
        int N; cin >> N;
        if(N == 0) break;

        bool check = false;
        for(int i=0; prime[i]<N; i++) {
            if(is_prime[N - prime[i]]) {
                cout << N << " = " << prime[i] << " + " << N - prime[i] << "\n";

                check = true;
                break;
            }
        }

        if(!check) cout << "Goldbach's conjecture is wrong.\n";
    }
}

 

에라토스테네스의 체를 활용하여 prime에 소수의 여부를 저장해주고, 짝수 N에 대해 N - prime[i] 역시 소수인지를 확인해주면 됩니다.

소수의 개수는 수가 커질수록 그 빈도가 감소하기 때문에 100만 이하에서 그렇게 많지 않습니다.

따라서 10만개의 테스트케이스가 주어지더라도 1초 안에 통과할 수 있습니다.

 

 

백준 BOJ 1916번 : 최소비용 구하기

Solved.ac 난이도 : Gold V

알고리즘 분류 : 다익스트라

 

M개의 간선과 비용이 주어질 때, A번째 도시에서 B번째 도시까지 가는데 필요한 최소 비용을 구하는 문제입니다.

간선의 비용이 주어지고 최단 거리를 구하는 문제이며, 음의 간선이 존재하지 않으므로 다익스트라 알고리즘을 사용하여 문제를 해결해주면 됩니다.

 

 

#include<bits/stdc++.h>
#define MAX 1001
using namespace std;
typedef pair<int, int> Pair;

int N, M;
vector<pair<int, int>> adj[MAX];
int dist[MAX];

void Dijkstra(int sour) {
    for(int i=1; i<=N; i++) dist[i] = INT_MAX;
    dist[sour] = 0;

    priority_queue<Pair, vector<Pair>, greater<Pair>> pq; // <distance, node>
    pq.push({0, sour});

    while(!pq.empty()) {
        int dist1 = pq.top().first;
        int curr = pq.top().second;

        pq.pop();

        if(dist[curr] < dist1) continue;

        for(int i=0; i<adj[curr].size(); i++) {
            int next = adj[curr][i].first;
            int dist2 = adj[curr][i].second;

            if(dist1 + dist2 < dist[next]) {
                dist[next] = dist1 + dist2;
                pq.push({dist[next], next});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cin >> N >> M;

    for(int i=0; i<M; i++) {
        int from, to, dist_; cin >> from >> to >> dist_;

        adj[from].push_back({to, dist_});
    }

    int sour, dest; cin >> sour >> dest;

    Dijkstra(sour);

    cout << dist[dest];
}

 

구현 자체는 워낙 정석적인 다익스트라 문제라서 큰 차이가 없습니다만, priority queue에서 pop 해주었을 때 dist[curr] (sour 정점에서 curr 정점까지의 거리)가 새로 pop한 distance보다 짧다면 이번에 pop한 데이터에 대해서 연산을 할 필요가 없으므로 continue를 해주면 됩니다.

 

if(dist[curr] < dist1) continue; 코드가 없어도 통과가 되는 문제가 있고 추가하지 않으면 시간 초과가 걸리는 문제가 있는데, 이것은 같은 두 정점을 잇는 간선이 여러 개 존재하느냐의 여부에 따라 갈립니다.

따라서 정석적으로 코드를 작성하기 위해서는 안정적으로 위의 continue 코드를 추가해준 형태를 암기하여 풀이하는 편이 좋습니다.

 

 

백준 BOJ 1406번 : 에디터

Solved.ac 난이도 : Silver I

알고리즘 분류 : 스택

 

초기 문자열이 주어지고, 일정 개수의 쿼리를 수행하는 문제입니다.

L이 입력되면 커서를 왼쪽으로 한 칸 옮기고 D가 입력되면 커서를 오른쪽으로 한 칸 옮깁니다.

B가 입력되면 커서 앞에 있는 문자를 삭제하고, P $가 입력되면 $라는 문자를 커서 왼쪽에 입력하도록 구현해야 합니다.

 

스택 두 개를 이용하여 풀면 간단하게 해결 가능한 문제입니다.

현재 커서를 기준으로 왼쪽에 있는 문자열은 왼쪽 스택에, 오른쪽에 있는 문자열은 오른쪽 스택에 넣어준 뒤 커서를 이동하거나 쿼리를 수행할 때 스택에 있는 문자들을 적절히 옮겨주면 빠른 시간 안에 모든 쿼리들을 수행할 수 있습니다.

 

 

#include<bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    string str; cin >> str;

    stack<char> L, R;
    for(int i=0; i<str.length(); i++) L.push(str[i]);

    int Q; cin >> Q;

    while(Q--) {
        char input; cin >> input;

        if(input == 'L' && !L.empty()) R.push(L.top()), L.pop();
        else if(input == 'D' && !R.empty()) L.push(R.top()), R.pop();
        else if(input == 'B' && !L.empty()) L.pop();
        else if(input == 'P') {
            char c; cin >> c;
            L.push(c);
        }
    }

    while(!L.empty()) R.push(L.top()), L.pop();

    while(!R.empty()) cout << R.top(), R.pop();
}