BOJ 1717 집합의 표현 / BOJ 15988 1, 2, 3 더하기 3 / BOJ 1699 제곱수의 합

백준 BOJ 1717번 : 집합의 표현

Solved.ac 난이도 : Gold IV

알고리즘 분류 : 그래프

 

0 ~ N으로 이루어진 각각의 집합과 M개의 쿼리가 주어질 때, 이 쿼리들을 적절히 수행하는 프로그램을 작성하는 문제입니다.

0 a b 꼴의 쿼리에 대해서는 a가 포함되어 있는 집합과 b가 포함되어 있는 집합을 합쳐야 합니다.

1 a b 꼴의 쿼리에 대해서는 a와 b가 같은 집합의 포함되어 있는지를 확인하여 같은 집합이라면 YES, 아니라면 NO를 출력하면 됩니다.

 

구현 자체는 큰 어려움이 없을 수 있지만 원소는 최대 100만, 쿼리는 최대 10만개가 주어질 수 있으므로 시간 안에 풀이 가능한 효율적인 알고리즘을 구현해야 합니다.

따라서 다음과 같이 구현합니다.

 

우선 parent 배열을 선언하여 각 원소의 parent를 저장하는 공간을 마련합니다.

root 함수를 만들어 parent를 재귀적으로 탐색하여 최상위 노드를 반환하는 기능을 구현합니다.

 

쿼리 0에 대해서는 a와 b에 대해 공통 root를 가지는지 확인하여 만약 다른 집합이라면 a의 parent를 b로 설정하여 두 그래프를 연결해줍니다.

쿼리 1에 대해서는 a와 b가 공통 root를 가지는지 확인하여 만약 같은 집합이라면 YES, 아니라면 NO를 출력해주면 됩니다.

 

이렇게 구현하면 모든 쿼리를 짧은 시간에 수행할 수 있습니다.

 

 

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

vector<int> parent;

int root(int v) {
    if(parent[v] == v) return v;
    return parent[v] = root(parent[v]);
}

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

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

    parent.resize(N+1);
    for(int i=0; i<=N; i++) parent[i] = i;

    while(M--) {
        int Q, u, v; cin >> Q >> u >> v;

        if(Q == 0) {
            u = root(u);
            v = root(v);

            if(u != v) parent[u] = v;
        }
        else if(Q == 1) {
            if(root(u) == root(v)) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}

 

 

백준 BOJ 15988번 : 1, 2, 3 더하기 3

Solved.ac 난이도 : Silver II

알고리즘 분류 : DP

 

정수 N을 1, 2, 3의 합으로 구하는 방법의 수를 구하는 문제입니다.

이 때 수를 합하는 순서가 다른 것은 다른 방법으로 간주한다는 조건이 있습니다. (4를 분해하는 방법인 1 + 3 = 3 + 1은 다른 방법입니다.)

 

분해하는 방법의 수에 대한 점화식을 간단하게 세울 수 있으므로 DP로 해결하면 됩니다.

N을 분해하는 방법의 수는 N-1을 분해하는 모든 경우에 1을 더하거나, N-2를 분해하는 모든 경우에 2를 더하거나, N-3을 분해하는 모든 경우에 3을 더하면 되므로 (일대일 대응이 가능하므로) 다음과 같이 점화식을 세울 수 있습니다.

 

dp[N] = dp[N-1] + dp[N-2] + dp[N-3] 

 

 

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

int dp[MAX] = {0, 1, 2, 4};

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

    for(int i=4; i<MAX; i++)
        dp[i] = ((dp[i-1] + dp[i-2]) % MOD + dp[i-3]) % MOD;

    int T; cin >> T;

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

        cout << dp[N] << "\n";
    }
}

 

다만 mod 값이 10^9 + 9이므로 세 수를 더했을 때 overflow가 발생할 수 있습니다.

따라서 dp 값을 저장할 때 long long의 자료형을 사용해주거나 또는 두 수를 더할 때마다 modulo 연산을 수행해주면 됩니다.

 

 

백준 BOJ 1699번 : 제곱수의 합

Solved.ac 난이도 : Silver III

알고리즘 분류 : DP

 

10만 이하의 자연수에 대해 최소 몇 개의 제곱수의 합으로 나타낼 수 있는지를 구하는 문제입니다.

조금 고민해보면 점화식을 세울 수 있다는 것을 알 수 있고, 따라서 DP로 풀이하기 위해 dp 공간을 N칸 이상 잡아줍니다.

 

그 다음 가장 먼저 dp[i*i]들에 대해서는 모두 1을 저장해주고, 다음과 같은 점화식을 활용하여 dp[N] 값을 구해주면 됩니다.

 

dp[i] = min(dp[i], dp[j*j] + dp[i - j*j])

(이 때 i는 2~N, j는 1 ~ sqrt(i))

 

 

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

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

    int N; cin >> N;

    vector<int> dp(N+1, INT_MAX);
    dp[0] = 0;

    for(int i=1; i*i<=N; i++) dp[i*i] = 1;

    for(int i=2; i<=N; i++)
        for(int j=1; j*j<=i; j++)
            dp[i] = min(dp[i], dp[j*j] + dp[i - j*j]);

    cout << dp[N];
}

 

 

참고로 이 문제에서는 N이 10만 이하이지만, 10^18 이하의 큰 수에 대해서도 풀이할 수 있습니다.

다만 해당 문제를 짧은 시간에 풀이하기 위해서는 "폴라드 로"라는 소인수분해를 대략 (O^(1/4))이라는 매우 짧은 시간에 수행 가능한 알고리즘을 활용해야 합니다.

 

[백준/BOJ C++] 17633번 : 제곱수의 합 (More Huge) (정수론, 폴라드 로, Diamond IV)

↑ 해당 문제의 풀이는 위의 링크에 정리되어 있으니, 풀이가 궁금하다면 한 번쯤 참고해보는 것도 좋을 것입니다.