백준 BOJ 2-SAT 알고리즘, 우선순위 큐 등 풀이 220826

백준 BOJ 11280번 : 2-SAT - 3

문제 난이도 : Platinum IV

알고리즘 분류 : SCC, 2-SAT

 

bool 변수 x1, ... , xn에 대해서 F = (xi ∨ xj) ∧ (xk ∨ xl) ∧ ... 와 같은 꼴의 식이 주어질 때, 변수들의 참 거짓을 적절히 설정하여 F의 값이 참이 되게 할 수 있는지 판별하는 문제이다.

 

(a ∨ b)와 같은 식이 있을 때 a가 거짓이면 b가 참, b가 거짓이면 a가 참이라는 두 개의 식을 얻을 수 있고 이렇게 2M개의 식을 얻은 뒤 x와 ~x가 모두 참인 식이 하나라도 나오면 불가능, 나머지 경우는 가능이다.

이것은 SCC로 풀이 가능한데, 2N개의 노드에 대해 2M개의 간선을 모두 연결한 그래프를 만든 후 a와 ~a가 같은 scc에 속해있는 경우 불가능임을 판별하면 되기 때문이다.

 

 

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

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> s;
vector<bool> ch;

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

        sort(v.begin(), v.end());

        scc.push_back(v);
    }

    return tmp;
}

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

    int N, M; cin >> N >> M;

    adj.resize(N*2);

    while(M--) {
        int a, b; cin >> a >> b;

        if(a < 0) a = (-a)*2 - 2;
        else a = a*2 - 1;

        if(b < 0) b = (-b)*2 - 2;
        else b = b*2 - 1;

        int na, nb;

        if(a % 2 == 0) na = a + 1;
        else na = a - 1;

        if(b % 2 == 0) nb = b + 1;
        else nb = b - 1;

        adj[na].push_back(b);
        adj[nb].push_back(a);
    }

    nnum.resize(N*2);
    cnum.resize(N*2);
    ch.resize(N*2);

    for(int i=0; i<N*2; i++)
        if(nnum[i] == 0) dfs(i);

    for(int i=0; i<N; i++) {
        if(cnum[i*2] == cnum[i*2 + 1]) {
            cout << 0 << "\n";
            return 0;
        }
    }

    cout << 1 << "\n";
}

 

백준 BOJ 1217번 : 하우스 M.D., 백준 BOJ 2207번 : 가위바위보, 백준 BOJ 3747번 : 완벽한 선거! 모두 이 문제와 동일한 문제이다.

 

백준 BOJ 11277번 : 2-SAT - 1 문제는 이 문제보다 범위가 작은 하위 문제로, 동일한 풀이 코드로 풀이할 수 있다.

 

 

백준 BOJ 18149번 : Length of Bundle Rope

문제 난이도 : Gold V

알고리즘 분류 : 우선순위 큐

 

N개의 줄의 길이가 주어지고, 길이가 a인 줄과 길이가 b인 줄을 연결하는데 a+b의 비용이 든다면, 모든 줄을 연결하는데 필요한 최소 비용을 구하는 문제이다.

 

a, b, c 3개의 줄을 연결한다고 생각해보자.

a와 b를 연결하면 a+b의 비용이 들고, 그 다음 연결된 a, b에 c를 연결하면 a+b+c의 비용이 들어 총 2a+2b+c의 비용이 든다.

이것으로 알 수 있는 사실은 먼저 연결한 줄의 비용이 더 든다는 것이다.

따라서 우선순위 큐로 짧은 줄의 길이가 top으로 오게 한 뒤 2개씩 top에서 꺼내어 합치고 비용을 더해주는 방식으로 문제를 풀이할 수 있다.

 

 

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

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

    int T; cin >> T;

    while(T--) {
        int N; cin >> N;

        priority_queue<int, vector<int>, greater<int>> pq;

        while(N--) {
            int x; cin >> x;

            pq.push(x);
        }

        int ans = 0;

        while(true) {
            int x = pq.top();
            pq.pop();

            if(pq.empty()) break;

            int y = pq.top();
            pq.pop();

            ans += x + y;
            pq.push(x + y);
        }

        cout << ans << "\n";
    }
}

 

 

백준 BOJ 6195번 : Fence Repair

문제 난이도 : Gold IV

알고리즘 분류 : 우선순위 큐

 

길이가 N개 부분 길이의 총합인 fence를 N개의 부분으로 나눌 때, 길이 a+b인 fence를 a, b로 나누는 비용이 a+b라고 한다면 fence를 N개의 조각으로 나누는 최소 비용을 구하는 문제이다.

 

조각을 나누는 것이 아니라 역으로 합쳐가면서 최소 비용을 구한다고 생각해보자.

그러면 a, b 두 조각을 합치는 비용이 a+b로 위의 문제 상황과 같은 상황이 된다.

따라서 동일한 코드로 풀이해줄 수 있다.

 

 

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

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

    int N; cin >> N;

    priority_queue<int, vector<int>, greater<int>> pq;

    while(N--) {
        int x; cin >> x;

        pq.push(x);
    }

    int ans = 0;

    while(true) {
        int x = pq.top();
        pq.pop();

        if(pq.empty()) break;

        int y = pq.top();
        pq.pop();

        ans += x + y;
        pq.push(x + y);
    }

    cout << ans << "\n";
}

 

 

백준 BOJ 11679번 : Canvas Painting

문제 난이도 : Gold IV

알고리즘 분류 : 우선순위 큐

 

N개의 구획으로 나누어진 캔버스를 칠하는 비용에 대한 규칙이 주어지고, 모든 구획을 다른 색으로 칠하기 위해 필요한 최소 비용을 구하는 문제이다.

 

규칙이 다른 문제에 비해서 복잡하게 되어있으나, 결국은 위의 상황들과 똑같이 치환시켜서 생각할 수 있다.

백준 BOJ 18149 문제와 동일한 풀이 코드로 정답 처리를 받을 수 있다.

 

 

백준 BOJ 13975번 : 파일 합치기 3

문제 난이도 : Gold IV

알고리즘 분류 : 우선순위 큐

 

N개의 파일이 있는데, 두 파일을 합칠 때 두 파일의 크기만큼 비용이 든다고 할 때, 모든 파일을 합치기 위해 필요한 최소 비용을 구하는 문제이다.

 

역시 위의 문제들과 동일한 상황이며, 똑같은 코드로 풀이 가능하다.

 

 

백준 BOJ 2696번 : 중앙값 구하기

문제 난이도 : Gold II

알고리즘 분류 : 우선순위 큐

 

값이 입력이 하나씩 들어오고, 홀수 번째 수가 입력될 때마다 그 때의 중앙값을 구하는 문제이다.

 

우선순위 큐 두 개를 이용하여, 양쪽의 수가 똑같아지도록 유지하면서 큐 두 개에 입력을 받으면 중앙값을 즉시 구할 수 있게 된다.

top에 최댓값이 오도록 하는 pq는 작은 수 절반을 저장하도록 하고, top에 최솟값이 오도록 하는 pq에는 큰 수 절반을 저장하도록 한다.

만약 top의 값의 크기 관계가 반대가 되었다면 가장 최근에 들어온 값 1개가 문제가 되는 것이므로 top에 있는 값의 위치만 바꾸어주면 우선순위 큐에 들어가서는 알아서 log 시간에 정렬이 된다.

 

 

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

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

    int T; cin >> T;

    while(T--) {
        int N; cin >> N;

        priority_queue<int> qx;
        priority_queue<int, vector<int>, greater<int>> qn;

        vector<int> v;

        for(int i=0; i<N; i++) {
            int x; cin >> x;

            if(qx.size() == qn.size()) qx.push(x);
            else qn.push(x);

            if(!qx.empty() && !qn.empty() && qx.top() > qn.top()) {
                int x = qx.top();
                int y = qn.top();

                qx.pop();
                qn.pop();

                qx.push(y);
                qn.push(x);
            }

            if(i % 2 == 0) v.push_back(qx.top());
        }

        cout << v.size() << "\n";

        for(int i=0; i<v.size(); i++) {
            cout << v[i] << " ";

            if(i % 10 == 9) cout << "\n";
        }

        cout << "\n";
    }
}

 

 

백준 BOJ 10166번 : 관중석

문제 난이도 : Silver II

알고리즘 분류 : 유클리드 호제법

 

 

 

위와 같이 반지름이 D인 원 위에 관중석이 일정한 간격으로 D개 있는 원이 D1 ~ D2에 분포되어 있을 때, 앞에 가려지지 않고 중심으로 도달할 수 있는 점들의 개수를 구하는 문제이다.

 

각도가 같으면 두 점 중 하나는 가려지게 되므로, 각도에 비례하는 값인 x/D (x = 1 ~ D) 값이 이전에 나온적 있는지를 체크하여 중복을 확인할 수 있다.

따라서 i = D1 ~ D2 범위에서, j = 1 ~ i 범위에서 모든 분수를 적어보고 기약분수로 만들어 이전에 나온적 있었는지 체크해보면 된다.

기약분수를 만드는 과정에서 시간 복잡도를 감소시키기 위해 유클리드 호제법이 사용된다.

 

 

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

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

    int N, M; cin >> N >> M;

    vector<vector<bool>> v(2001, vector<bool>(2001));
    int ans = 0;

    for(int i=N; i<=M; i++)
        for(int j=1; j<=i; j++) {
            int a = i / __gcd(i, j);
            int b = j / __gcd(i, j);

            if(!v[a][b]) ans++;

            v[a][b] = true;
        }

    cout << ans << "\n";
}

 

 

백준 BOJ 11501번 : 주식

문제 난이도 : Silver II

알고리즘 분류 : 그리디

 

N개의 일이 주어지고 각 날짜의 주식의 가격이 주어질 때, 각 날마다 주식을 1개 사거나 또는 1개 이상 매도할 수 있다고 할 때, N일 후에 취할 수 있는 이득의 최댓값을 구하는 문제이다.

 

뒤에서 앞으로 오면서 지금까지 나온 최댓값에서 현재 가격을 뺀 가격만큼 매일 이득을 볼 수 있다.

따라서 최댓값을 기록하면서 현재 가격을 뺀 값들을 합쳐주면 된다.

 

 

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

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

    int T; cin >> T;

    while(T--) {
        int N; cin >> N;

        vector<int> v(N);
        for(int i=0; i<N; i++) cin >> v[i];

        int Max = 0, ans = 0;

        for(int i=N-1; i>=0; i--) {
            Max = max(Max, v[i]);

            ans += Max - v[i];
        }

        cout << ans << "\n";
    }
}

 

 

백준 BOJ 9253번 : 스페셜 저지

문제 난이도 : Bronze II

알고리즘 분류 : 문자열

 

문자열 a, b, c가 주어질 때 a, b의 최대 일치 부분 수열이 c인지 검사하는 문제이다.

 

a.find(c)는 a에서 c가 나타나는 첫 주소를 반환하고 이를 활용하여 풀이를 구현할 수 있다.

a에 c가 포함되지 않는 경우 a.find(c) 값은 매우 큰 양수를 가지므로, 이것이 a.length()보다 크거나 같은지 검사하여 c가 문자열에 포함되지 않음을 확인할 수 있다.

 

 

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

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

    string a, b, c; cin >> a >> b >> c;

    if(a.find(c) >= a.length() || b.find(c) >= b.length()) {
        cout << "NO\n";
        return 0;
    }

    bool check = true;

    if(a.find(c) > 0 && b.find(c) > 0 && a[a.find(c)-1] == b[b.find(c)-1]) check = false;
    if(a.find(c) + c.length() < a.length() && b.find(c) + c.length() < b.length()
       && a[a.find(c) + c.length()] == b[b.find(c) + c.length()]) check = false;

    if(check) cout << "YES\n";
    else cout << "NO\n";
}

 

 

백준 BOJ 24957번 : Loop of Chocolate

문제 난이도 : Bronze II

알고리즘 분류 : 기하학, 구현

 

3차원 공간 상에서 N개의 구의 좌표가 주어질 때, 구의 총 부피를 구하는 문제이다.

 

문제는 구가 겹치는 경우가 발생한다는 것인데, 반지름이 r인 두 구 사이의 거리가 d(< 2r)일 때 겹치는 공간의 부피는 다음과 같다. (문제에서 알려준다.)

 

 

 

따라서 N개의 구의 부피를 더하고, 거기에서 2중 for문으로 일일이 쌍을 대조해보면서 겹치는 부피들을 빼주면 된다.

 

 

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

struct s { double x, y, z; };

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

    double N, r; cin >> N >> r;

    vector<s> v(N);
    for(int i=0; i<N; i++)
        cin >> v[i].x >> v[i].y >> v[i].z;

    double ans = N * 4.0 / 3.0 * M_PI * r * r * r;

    for(int i=0; i<N; i++)
        for(int j=i+1; j<N; j++) {
            double d = sqrt(pow(v[i].x - v[j].x, 2) + pow(v[i].y - v[j].y, 2) + pow(v[i].z - v[j].z, 2));

            if(d >= r*2) continue;

            double vol = 2.0 / 3.0 * M_PI * pow(r - d/2, 2) * (2*r + d/2);

            ans -= vol;
        }

    cout << fixed;
    cout.precision(7);

    cout << ans << "\n";
}