나를 위한 기록

문제 링크: https://acmicpc.net/problem/5782 

문제를 요약해봅시다.

• 주어진 $N$개의 문장은 각각 다른 문장 $X$의 참, 거짓 여부를 가리킵니다.
• 문장의 참, 거짓 여부를 조사하여 만약 모순이면 Inconsistent를, 모순이 아니면 참이 될 수 있는 문장의 최대 개수를 출력합니다.

- 사실 관계 유추

어떤 문장 $X$의 내용이 "문장 $Y$는 참이다" 라고 합시다. 이때 유추할 수 있는 사실은 다음의 2가지입니다.

• 문장 $X$가 참이면, 문장 $Y$도 참입니다.
• 문장 $X$가 거짓이면, 문장 $Y$도 거짓입니다.

이때 이 두 명제의 역도 성립합니다. 왜냐하면, 문장 $Y$가 참이면 문장 $X$가 참을 말하고 있는 것이기 때문입니다! 문장 $Y$가 거짓인 경우도 비슷합니다.

이와 유사하게, 문장 $X$의 내용이 "문장 $Y$는 거짓이다" 인 경우도 생각해 볼 수 있습니다. 이때 유추할 수 있는 사실은,

• 문장 $X$가 참이면, 문장 $Y$는 거짓입니다.
• 문장 $X$가 거짓이면, 문장 $Y$는 참입니다.

이 두 명제의 역도 역시나 성립합니다.

- 문제 구성 (그래프)

이러한 문장 간의 사실 관계를 나타낼만한 좋은 자료구조가 없을까요? 바로 그래프입니다.

그래프를 이용해서 문장 간의 관계를 표현해봅시다.

• 문장 $X$가 참인 경우와 거짓인 경우를 각각 정점 $x$, $\neg x$로 쓰겠습니다.
• 문장 $X$의 내용이 "문장 $Y$는 참이다" 이면, 두 정점 $x, y$를 잇는 양방향 간선과 두 정점 $\neg x, \neg y$를 잇는 양방향 간선을 추가합니다.
• 문장 $X$의 내용이 "문장 $Y$는 거짓이다" 이면, 두 정점 $x, \neg y$를 잇는 양방향 간선과 두 정점 $\neg x, y$를 잇는 양방향 간선을 추가합니다.

이때 양방향 간선을 쓰는 이유는, 각 문장이 만드는 2가지 명제가 그 역 또한 성립하는 명제들이기 때문입니다.

- 그래프 탐색

그래프를 구성했으니 이제 그래프를 탐색하면서 문장 간의 모순을 발견하거나 답을 구해봅시다. 탐색은 아무 방법이나 괜찮다고 생각하지만 이 글에서는 DFS를 사용하겠습니다.

간선으로 이어진 두 정점은 둘 다 참이거나 둘 다 거짓입니다. 즉 같은 그룹에 속한다고 볼 수 있습니다. 여기서 모순을 발견하려면 그래프를 탐색하다가, $x$와 $\neg x$가 같은 그룹에 속하는지를 찾아주면 됩니다. $x$와 $\neg x$는 절대로 같은 그룹에 속할 수 없기 때문입니다.

이걸 효과적으로 해결하려면 각 정점을 2가지 색으로 칠하면 됩니다. DFS로 방문하는 정점들의 색을 전부 색 1로 칠하고, 방문한 정점의 역에 해당하는 정점을 색 2로 칠해줍시다. 만약 탐색 중에 색 2인 정점을 탐색해야 된다면 모순이라는 것을 알 수 있습니다.

모순이 없다면 탐색한 정점들 중 문장이 참이 되게 하는 정점, 즉 $\neg$ 가 붙지 않은 정점 중 색 1로 칠해진 것의 개수를 세면 참이 되는 문장의 개수를 구할 수 있습니다.

그런데 색 2로 칠해진 문장이 더 많다면 어떻게 해야 할까요? 이때는 그냥 색 1과 색 2를 바꾸면 결과가 똑같기 때문에, 그냥 둘 중에 더 많은 것을 쓰면 됩니다.

여기서 주의해야 할 점은, 그래프가 연결 그래프면 좋겠지만 연결 그래프가 아닐 수 있다는 것입니다. 따라서 그래프의 모든 연결 요소를 다 처리할 때 까지 DFS를 잊지 말고 돌려주도록 합시다!

시간 복잡도는,

• DFS를 모든 정점에 대해 실행하고, 정점의 수가 $2N$, 간선의 수가 $2N$이므로 $O(2N + 2N) = O(N)$

따라서 총 $O(N)$입니다.

공간 복잡도는,

• 정점 $2N$개와 간선 $2N$개를 저장하므로 $O(2N + 2N) = O(N)$

따라서 총 $O(N)$입니다.

소스코드 (C++)

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef __int128 xll;

// 매 탐색마다 방문한 문장의 수
int group = 0;
// 매 탐색마다 방문한 문장 중, 문장을 참으로 만들면서 색 1로 칠해진 문장의 수
int colored = 0;

// DFS를 하는 함수입니다. 모순이면 true를, 그 외에는 false를 반환합니다.
bool dfs(vector<int> &truth, vector<vector<int>> &edges, int n, int v) {
    // 방문 중인 정점을 색 1로 칠합니다.
    truth[v] = 1;
    group++;
    
    // 현재 문장의 역에 해당하는 정점은 색 2로 칠합니다. 
    if (v > n) truth[v - n] = 2;
    else {
    	// 방문 중인 정점이 문장이 참이 되는 경우라면 개수를 세줍니다.
        colored++;
        truth[v + n] = 2;
    }
    
    bool result = false;
    for (int c: edges[v]) {
        if (truth[c] == 0) {
        	// 만약 이웃한 정점이 방문하기 전이라면, 탐색을 시도합니다.
            result = result || dfs(truth, edges, n, c);
        }
        else if (truth[c] == 2) {
            // 만약 이웃한 정점의 색이 색 2라면 모순입니다.
            return true;
        }
    }
    
    return result;
}

int main() {
    fastio;
    
    string ts = "true.";
    string fs = "false.";
    
    while (1) {
        int n;
        cin >> n;
        
        if (n == 0) break;
        
        vector<int> truth(2 * n + 1);
        vector<vector<int>> edges(2 * n + 1);
        
        for (int i = 1; i <= n; i++) {
            string sen;
            int j;
            
            cin >> sen >> j >> sen >> sen;
            
            // 문장 간의 사실 관계를 나타내는 그래프를 구축합니다.
            if (sen == ts) {
                edges[i].push_back(j);
                edges[j].push_back(i);
                edges[i + n].push_back(j + n);
                edges[j + n].push_back(i + n);
            }
            else {
                edges[i].push_back(j + n);
                edges[j].push_back(i + n);
                edges[i + n].push_back(j);
                edges[j + n].push_back(i);
            }
        }
        
        bool incons = false;
        int cnt = 0;
        for (int i = 1; i <= n && !incons; i++) {
        	// 아직 탐색하지 않은 문장이 있다면 DFS로 탐색하며 정점의 색을 칠합니다.
            if (truth[i] == 0) {
                // 각 탐색마다 탐색한 문장의 수, 참 문장의 수를 구합니다.
                group = 0;
                colored = 0;
                
                // 탐색을 시도합니다.
                if (dfs(truth, edges, n, i)) incons = true;
                else {
                    // 탐색이 성공적이라면 참이 될 수 있는 문장의 수를 더해줍니다.
                    cnt += max(colored, group - colored);
                }
            }
        }
        
        if (incons) {
            cout << "Inconsistent\n";
            continue;
        }
        
        cout << cnt << "\n";
    }
}

문제 링크: https://acmicpc.net/problem/10989 

문제를 요약해봅시다.

• 주어진 $N$개의 수를 오름차순으로 정렬하여 출력합니다.

문제의 조건을 읽어보면 $N \le 10,000,000$으로 $N$의 제한이 매우 큰 것을 볼 수 있습니다.

이 정도 제한이면 병합 정렬이나 퀵 정렬같은 $O(N \log N)$의 시간복잡도를 갖는 정렬 알고리즘으로는 시간 제한에 맞추지 못할 수 있습니다. 엎친데 덮친 격으로 메모리 제한이 8MB이므로 $10,000,000$개 수를 다 저장하는 위의 알고리즘들로는 메모리 초과가 발생하게 됩니다.

따라서 널리 알려진 방법들은 사용할 수 없습니다. 어떻게 해야 할까요?

문제의 핵심은 주어지는 수들의 범위가 구간 $[1, 10000]$에 속한다는 것입니다.

수의 범위가 꽤 작기 때문에 각 수가 몇 번 등장했는지만 세어 주면 문제를 해결할 수 있습니다.

예를 들어 1 5 2 3 4 5 3 3 이 들어온다면 1이 1번, 2가 1번, 3이 3번, 4가 1번, 5가 2번이므로 1 2 3 3 3 4 5 5 를 얻을 수 있습니다.

시간복잡도는 입출력을 각각 $N$번 하므로 $O(N)$이고, 공간복잡도는 $O(10000) = O(1)$입니다.

소스코드 (C++)

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef __int128 xll;

int main() {
    fastio;
    
    int n;
    cin >> n;
    
    // 각 수가 몇 번 등장했는지 기록하는 배열입니다.
    vector<int> cnt(10001);
    
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        
        cnt[x]++;
    }
    
    // 기록된 횟수만큼 해당 수를 출력합니다.
    for (int i = 1; i <= 10000; i++) {
        for (int j = 0; j < cnt[i]; j++) {
            cout << i << "\n";
        }
    }
}

문제 링크: https://acmicpc.net/problem/24461 

문제를 요약해봅시다.

• 주어진 그래프는 사이클이 없고 간선이 $N - 1$개이므로 트리입니다.
• 가장자리 정점은 연결된 간선이 1개인 정점이고, 줄기는 가장자리 정점이 2개 이하인 그래프입니다.
• 트리의 가장자리 정점이 2개 이하가 될때까지 가장자리 정점을 지우는 것을 반복하고, 최후에 남은 정점의 목록을 출력해야 합니다.

이 문제는 주어진 내용을 구현하기만 하면 되는 문제입니다. 다음 과정을 반복하면 되는데요,

• 간선의 개수가 1인 정점들을 모은 후,
• 그 정점들을 모두 지우고, 연결되어 있던 정점들의 간선 수를 1개씩 줄입니다.

이는 위상 정렬 문제에서 볼 수 있는 기법과 비슷합니다. 답을 구현하기 위해서는 각 정점의 간선 수를 기록하는 배열과, 각 정점의 제거 여부를 기록하는 배열이 필요합니다. 위상 정렬 문제를 풀어보셨다면 쉽게 구현할 수 있습니다.

그러나 일반적인 위상 정렬 문제와 다르게 이 문제에서는 유의해야 할 부분이 있습니다. 매 반복마다 모든 정점이 동시에 제거된다는 것인데요.. 이는 매 반복마다 큐의 크기를 기록하고, 그 큐의 크기만큼만 반복하는 방법으로 구현하면 됩니다.

시간복잡도는,

• 정점의 간선 수를 기록하는데 \(O(N)\)
• \(O(N)\)개의 간선을 조사하므로 \(O(N)\)

총 \(O(N)\)의 시간복잡도를 갖습니다.

소스코드 (C++)

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef __int128 xll;

int main() {
    fastio;
    
    int n;
    cin >> n;
    
    vector<vector<int>> edges(n);
    vector<bool> exc(n);	// 정점의 제거 여부를 저장
    vector<int> neigh(n);	// 정점의 이웃 수를 저장
    
    // 그래프의 간선 배열을 만들고, 각 정점의 이웃 수를 계산합니다.
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        
        edges[u].push_back(v);
        edges[v].push_back(u);
        
        neigh[u]++;
        neigh[v]++;
    }
    
    // 가장자리 정점을 삽입하는 큐입니다.
    queue<int> q;
    
    // 가장자리 정점의 수를 셉니다.
    int ec = 0;
    for (int i = 0; i < n; i++) {
        if (neigh[i] == 1) {
            ec++;
        }
    }
    
    // 가장자리 정점의 수가 3개 이상이면 큐에 정점들을 삽입합니다.
    if (ec > 2) {
        for (int i = 0; i < n; i++) {
            if (neigh[i] == 1) {
                q.push(i);
                exc[i] = true;
            }
        }
    }
    
    // 그래프가 줄기만 남게 될때까지 가장자리 정점을 제거합니다.
    while (1) {
    	// 큐의 크기가 2 이하, 즉 그래프가 줄기만 남게 되면 종료합니다.
        int loop = q.size();
        if (loop <= 2) break;
        
        vector<int> next_elems;
        
        for (int i = 0; i < loop; i++) {
            int v = q.front();
            q.pop();
            
            // 큐에 담긴 정점들을 제거하고, 이웃한 정점들의 이웃 수를 1 줄입니다.
            for (int c: edges[v]) {
                if (!exc[c] && --neigh[c] == 1) {
                    next_elems.push_back(c);
                    q.push(c);
                }
            }
        }
        
        if (next_elems.size() <= 2) break;
        
        for (int x: next_elems) {
            exc[x] = true;
        }
    }
    
    for (int i = 0; i < n; i++) {
        if (!exc[i]) cout << i << " ";
    }
}

문제 링크: https://acmicpc.net/problem/11616 

문제를 요약해봅시다.

• 주어진 $n$자리의 수열을 분할해 부분 수열로 만들되, 모든 부분 수열이 나타내는 정수가 $m$으로 나누어 떨어지도록 나누는 경우의 수를 계산해야 합니다.
• 예를 들면, 수열 $1246$을 $2$로 나누어 떨어지게 만드는 방법은 $[12, 4, 6], [124, 6], [12, 46], [1246]$의 $4$가지입니다.

수열을 조건에 맞게 임의로 분할하여 만든 부분 수열들을 $s_1, s_2, ... , s_k$라 합시다. 이때 다음이 성립합니다.

• 모든 부분 수열 $s_1, s_2, ... , s_k$이 나타내는 자연수는 $m$으로 나누어 떨어집니다.
• 임의의 인접한 두 부분 수열 $s_i, s_{i + 1}$을 이어 붙인 부분수열 $s_i s_{i+1}$ 역시 $m$으로 나누어 떨어집니다.

2번째 성질이 성립하는 이유를 알아봅시다. 부분 수열 \(s_i\)가 나타내는 자연수의 값을 \(x_i\)라 하고, \(x_i\)의 자릿수를 \(d_i\)라 하겠습니다. 이때 이어 붙여서 생긴 부분 수열 \(s_i s_{i+1}\)이 나타내는 자연수의 값은 \(x_i \times 10^{d_i} + x_{i+1}\)이 됩니다.

그런데 \(x_i, x_{i + 1}\)이 모두 \(m\)으로 나누어 떨어지므로, \(x_i \times 10^{d_i} + x_{i+1}\)도 \(m\)으로 나누어 떨어집니다.

이 성질을 이용하면, 처음에 주어진 \(n\)자리의 순열을 \(m\)으로 나누어 떨어지는 최소 크기의 부분 수열들로 앞에서부터 분할한 뒤 분할의 개수를 세는 것으로 문제를 해결할 수 있습니다.

예제인 \([1246], m = 2\) 의 경우 \([12, 4, 6]\)으로 분할을 할 수 있고, \(12\)와 \(4\) 사이의 분할과 \(4\)와 \(6\) 사이의 분할, 합계 \(2\)번의 분할이 있습니다. 이때 이 \(2\)개의 분할 각각을 해도 되고 하지 않아도 되는데, 분할을 하지 않아도 위에서 다룬 2번째 성질 때문에 부분 수열이 \(m\)으로 나누어 떨어지기 때문입니다. 따라서, 분할의 개수를 \(p\)라 했을 때 \(2^p\)가 답이 됩니다.

우리가 분할해서 얻은 수열들을 이어 붙여 얻을 수 있는 부분 수열들이 아닌 것 중에도 \(m\)으로 나눠지는 것들이 있으나, 이것들을 선택하면 부분 수열들을 전부 다 \(m\)으로 나누어 떨어지게 만들 수가 없습니다. 이러한 부분 수열들은 앞에서부터 분할해서는 등장하지 않기 때문입니다.

마지막으로, 어떻게 분할해도 모든 부분 수열을 \(m\)으로 나누어 떨어지게 할 수 없다면 \(0\)을 출력해야 합니다. 사소한 예외이니 놓치지 않도록 합시다.

시간복잡도는..

• 수열의 모든 숫자들을 한 번씩 순회하며 부분 수열로 분할하므로 \(O(n)\)
• 분할의 개수 \(p\)를 세고 \(2^p\)를 구해야 하고, 분할의 최대 개수가 \(n - 1\)개이므로 \(O(p) = O(n)\), 분할 정복을 이용하여 거듭제곱을 최적화하면 \(O(\log n)\)

총 \(O(n + \log n) = O(n)\)입니다.

소스코드 (C++)

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef __int128 xll;

int main() {
    fastio;
    
    ll n, m;
    cin >> n >> m;
    
    string s;
    cin >> s;
    
    ll mod = 1e9 + 7;
    
    // 앞에서부터 수열을 분할합니다.
    ll partitions = 0;
    ll current_division = 0;
    for (int i = 0; i < n; i++) {
        ll x = s[i] - '0';
        ll value = x % m;
        
        // 현재 탐색하고 있는 부분 수열을 m으로 나눈 값을 계산합니다.
        current_division = (current_division * 10 + value) % m;
        
        // 만약 m으로 나눈 값이 0이라면, 분할을 발견한 것입니다.
        // 분할의 개수를 1 증가시킵니다.
        if (current_division == 0) {
            partitions++;
        }
    }
    
    if (current_division) {
    	// m으로 나누어 떨어지게 분할하는 것이 불가능하면 0을 출력합니다.
        cout << 0;
    }
    else {
    	// 마지막으로 경우의 수를 구합니다.
        ll k = partitions - 1;
        ll f = 2;
        ll result = 1;
        while (k) {
            if (k % 2) result = (result * f) % mod;
            f = (f * f) % mod;
            k /= 2;
        }
        cout << result;
    }
}

문제 링크: https://acmicpc.net/problem/28251 

문제를 요약해봅시다.

• 각 나도리는 각각 어떤 그룹 $G_x$에 속해 있으며, 그룹 $G_x$의 전투력은 $G_x$에 속한 서로 다른 두 나도리의 크기의 곱의 총합, 즉 $\sum_{i, j \in G_x, i < j}s_i s_j$입니다.
• 쿼리 $a\\;b$가 들어오면 나도리 $a$와 $b$가 속한 그룹을 합쳐 하나의 그룹으로 만들고, 합쳐진 그룹의 전투력을 출력해야 합니다.
• 문제에 정확히 나와 있지는 않는 것 같지만, 모든 나도리는 처음에 자기 자신만이 속한 크기 1인 그룹에 속해 있습니다.

각 나도리는 반드시 하나의 그룹에만 속해야 하고, 두 그룹을 합칠 수 있다고 하니 분리 집합으로 풀어봅시다.

최초에 모든 나도리는 자기 자신만이 속한 그룹에 있으므로 모든 그룹의 전투력은 $0$입니다.

이후 쿼리 $a\;b$가 들어오면, $a$가 속한 그룹과 $b$가 속한 그룹을 합친 후 전투력을 계산하여 출력한 후 저장하면 됩니다.

이제 전투력을 계산해봅시다. 그룹 \(X\)와 그룹 \(Y\)를 합치는 상황을 생각해 봅시다.

\(X\)의 크기를 \(p\)라 하고, 여기에 속한 나도리를 각각 \(x_1, x_2, x_3, ... , x_p\)라 합시다. 비슷하게 \(Y\)의 크기를 \(q\)라 하고, 여기에 속한 나도리를 각각 \(y_1, y_2, y_3, ... , y_q\)라 합시다.

전투력을 구하려면 각각의 \(x_i\)와 \(y_j\)를 모두 곱해서 더해보면 되겠지만.. 나도리의 수가 \(N\leq 200,000\)으로 상당히 크므로 그룹을 합칠 때마다 전부 계산하는 것은 시간초과가 날 것입니다. 계산을 줄여봅시다.

그룹의 전투력은 그룹 내 서로 다른 두 나도리의 크기의 곱을 모두 합한 것입니다. \(X\)와 \(Y\)를 합친 새로운 그룹의 전투력을 구하는데는 다음 세 가지 종류의 나도리 쌍을 생각해야 합니다.

• 두 나도리 모두 원래 \(X\)에 속해 있던 나도리인 경우.
• 두 나도리 모두 원래 \(Y\)에 속해 있던 나도리인 경우.
• 두 나도리 중 하나는 \(X\)에, 하나는 \(Y\)에 속해 있던 나도리인 경우.

두 나도리가 모두 \(X\)에 속해 있던 경우, 이 나도리 쌍들의 크기의 곱을 모두 더한 것은 \(X\)의 전투력과 같다는 것을 알 수 있습니다. 비슷하게, 둘 다 \(Y\)에 속해 있던 경우는 \(Y\)의 전투력과 같다는 것을 알 수 있습니다.

따라서 세 번째 경우인 하나는 \(X\)에 속해 있었고, 나머지 하나는 \(Y\)에 속해 있었던 경우를 생각해봅시다.

\(X\)에 속해 있던 나도리 중 \(Y\)에도 속해 있던 나도리는 없습니다. 왜냐하면 각 나도리는 하나의 그룹에만 들어 있기 때문입니다.

그렇다면, \(X\)의 나도리의 크기 \(s_{x_i}\)에 대해 \(y_1, y_2, ... , y_q\)의 크기를 각각 곱하고, 모두 더해주면 됩니다.

식으로 표현하면 다음과 같습니다.

\[\sum_{i=1}^{p}s_{x_i}\times\sum_{j=1}^{q}s_{y_j}\]

즉, 원래 \(X\)에 속해 있던 나도리의 크기의 합과 \(Y\)에 속해 있던 나도리의 크기의 합을 곱해주면 되는겁니다!

따라서 새로운 그룹의 전투력은 다음 식으로 표현할 수 있게 됩니다. 그룹 \(X, Y\)의 전투력을 각각 \(P_X, P_Y\)라 하면,

\[P_{X \cup Y} = P_X + P_Y + \sum_{i=1}^{p}s_{x_i}\times\sum_{j=1}^{q}s_{y_j}\]

입니다. 이를 쉽게 구현하려면 각 그룹의 전투력 뿐 아니라, 그룹에 속한 나도리들의 크기 합도 저장해두면 됩니다.

시간 복잡도는 다음과 같습니다.

• 크기 \(O(N)\)인 배열을 분리 집합 연산을 위해 초기화하므로 \(O(N)\)
• 분리 집합 연산은 아커먼 역함수에 비례하는 시간 복잡도를 갖고, 이를 \(Q\)번 반복하므로 \(O(Q\alpha(N))\)

아커먼 역함수가 굉장히 작아 사실 \(O(1)\)로 생각한다면, 총합 \(O(N + Q)\)의 시간 복잡도를 갖게 됩니다.

소스코드 (C++)

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;

// 그룹의 크기 합을 저장
vector<ll> set_sum;
// 그룹의 전투력을 저장
vector<ll> set_power;
vector<ll> parent;

// 그룹 검색 연산
int find_parent(int v) {
    if (v == parent[v]) return v;
    else return parent[v] = find_parent(parent[v]);
}

// 그룹 병합 연산
void union_parent(int v1, int v2) {
    int p1 = find_parent(v1);
    int p2 = find_parent(v2);
    
    if (p1 > p2) swap(p1, p2);
    
    if (p1 != p2) {
        parent[p1] = p2;
        set_power[p2] = set_power[p1] + set_power[p2] + set_sum[p1] * set_sum[p2];
        set_sum[p2] = set_sum[p1] + set_sum[p2];
    }
}

int main() {
    fastio;
    
    int n, q;
    cin >> n >> q;
    
    set_sum = vector<ll>(n + 1);
    set_power = vector<ll>(n + 1);
    parent = vector<ll>(n + 1);
    
    for (int i = 1; i <= n; i++) {
        cin >> set_sum[i];
        parent[i] = i;
    }
    
    while (q--) {
        int a, b;
        cin >> a >> b;

        union_parent(a, b);
        cout << set_power[find_parent(a)] << "\n";
    }
}

문제 링크: https://acmicpc.net/problem/27925 

문제를 요약해봅시다.

• 온도가 0에서 9인 공간 3개를 가진 인덕션 위에서, 총 \(N\)개의 음식을 순서대로 하나씩 조리해야 합니다.
• 각 공간의 온도는 온도 버튼을 누르면 1 증가하거나 1 감소하고, 0이거나 9일 때는 각각 9, 0으로 온도가 변화할 수 있습니다.
• 온도 버튼을 누르는 횟수의 총합을 최소화해야 합니다.

버튼을 누르는 횟수

먼저 버튼을 누르는 횟수를 계산해봅시다. 현재 인덕션의 온도가 \(t_0\)이고, 조리해야 하는 음식의 온도가 \(t_1\)이라 합시다.

온도는 + 버튼을 눌러 맞추는 방법과 - 버튼을 눌러 맞추는 방법이 있습니다.

+ 버튼을 눌러 온도를 맞추는 경우부터 생각해 봅시다.

• \(t_1 \ge t_0\)이면 \(t_1 - t_0\)회 눌러야 합니다. 자명합니다.
• \(t_1 < t_0\)이면 \(10 + t_1 - t_0\)회 눌러야 합니다. 예를 들어, \(t_0 = 7, t_1 = 3\)이면 + 버튼을 눌러서 7에서 3까지 가려면 \(10 + 3 - 7 = 6\)번을 눌러야 합니다.

이것과 비슷하게 - 버튼을 눌러 맞추는 경우는 다음과 같습니다.

• \(t_0 \ge t_1\)이면 \(t_0 - t_1\)회 눌러야 합니다. 역시 자명합니다.
• \(t_0 < t_1\)이면 \(10 + t_0 - t_1\)회 눌러야 합니다.

그런데, 우리는 버튼이 어떤 경우에도 최대 9번까지만 눌릴 수 있다는 것을 알고 있습니다. 따라서 각 식을 10으로 나눈 나머지를 취할 수 있고, 이는 식을 아래와 같이 변형할 수 있게 해줍니다.

\[(t_1 - t_0)\,\%\,10 = (10 + t_1 - t_0)\,\%\,10\]

버튼을 누르는 횟수에 대한 식을 이렇게 간략하게 할 수 있으므로, + 버튼과 - 버튼을 누르는 횟수 중 더 작은 것을 고르면 됩니다.

이를 함수 \(f\)라 쓰면 \(f(t_0, t_1) = min((10 + t_1 - t_0)\,\%\,10, (10 + t_0 - t_1)\,\%\,10)\)이 됩니다.

접근법 - 그리디?

이제 문제를 어떻게 풀지 생각해 봅시다. 가장 먼저 떠오를 만한 것은 그리디한 접근법입니다.

• 3개 인덕션의 온도를 각각 기록하고, 새로운 음식이 들어오면 3개 인덕션 중 가장 버튼을 적게 누를 수 있는 인덕션을 골라 그 인덕션의 온도를 변경하고, 버튼을 누른 횟수를 기록합니다.
• 버튼을 누른 횟수의 총합을 구합니다.

이 방법은 얼핏 보기엔 잘 작동할 수 있으나 문제점이 있습니다. 바로 가장 버튼을 적게 누를 수 있는 인덕션이 2개 이상인 경우입니다.

예를 들어봅시다. 인덕션의 온도가 각각 6, 0, 0 일때 온도 3인 음식을 조리하려고 하면 온도가 6인 인덕션을 온도 3으로 바꿀지, 온도가 0인 인덕션을 온도 3으로 바꿀지 알 수 없습니다. 두 경우 중 아무거나 선택하기엔 뒤의 음식이 어떤게 나올 지 모릅니다.

만약 다음 음식이 온도 4에서 조리해야 하는 온도라면 온도 6인 인덕션을 3으로 바꾸는 것이 유리하고, 다음 음식이 온도 5에서 조리해야 하는 온도라면 온도 0인 인덕션을 온도 3으로 바꾸는 것이 유리합니다.

그러면 뒤에 들어올 음식들의 온도를 고려해서 바꾸면 되지 않느냐 할 수 있지만... 저는 어떻게 해야할 지 모르겠습니다.

다른 방법으로 접근해 보겠습니다.

접근법 - 다이나믹 프로그래밍

접근 방식을 바꿔서 다이나믹 프로그래밍을 활용해 봅시다. 2차원 배열 \(dp\)를 정의합시다.

\(dp[i][j]\)를 \(i\)번째 음식을 조리한 후 인덕션 3개의 온도 상태가 \(j\) 일 때, 지금까지 버튼을 누른 횟수의 최솟값이라 하겠습니다.

온도 상태는 인덕션 온도가 각각 \(a, b, c\)일때 이들을 이어붙인 수 \(abc\)로 하겠습니다. 왜냐하면 온도가 각각 한 자리 수이기 때문에 세 온도를 다 이어붙이면 구간 \([0, 999]\)의 정수가 되기 때문입니다. 정수가 되면 배열 인덱스로 관리하기도 편합니다!

최초 상태는 음식을 하나도 조리하지 않았고, 온도도 전부 0이기 때문에 \(dp[0][0] = 0\)이 됩니다.

이제 \(dp[i][j]\)의 항들에 관한 식을 생각해 봅시다.

\(j = abc\)라 하고, 다음 음식의 온도를 \(t\)라 하겠습니다.

• 만약 1번째 인덕션을 \(t\)로 바꾼다면, \(dp[i + 1][tbc] = dp[i][abc] + f(a, t)\)입니다.
• 만약 2번째 인덕션을 \(t\)로 바꾼다면, \(dp[i + 1][atc] = dp[i][abc] + f(b, t)\)입니다.
• 만약 3번째 인덕션을 \(t\)로 바꾼다면, \(dp[i + 1][abt] = dp[i][abc] + f(c, t)\)입니다.

만약 다음 \(dp\)값을 계산했는데 이미 계산된 값보다 더 크다면 더 계산할 필요가 없습니다. 왜냐하면 같은 개수의 음식을 조리했고 같은 온도 상태인데, 이번에 계산한 방법이 버튼을 누른 횟수가 다른 방법보다 더 많다면 이번 방법은 이미 버튼을 몇 번 더 누른 상태이므로 볼 필요가 없습니다.

이를 \(N\)개 음식에 대해, 각각의 온도 상태 \([0, 999]\)에 대해서 반복해주면 됩니다.

시간복잡도는 \(O(N \times 1000) = O(N)\), 공간 복잡도는 \(O(N \times 1000) = O(N)\)입니다.

메모리 최적화 - \(O(1)\)

위의 점화식을 잘 보면 \(dp[i + 1]\)을 계산하는 데 \(dp[i]\)의 값만이 쓰이는 것을 알 수 있습니다.

즉 바로 직전의 값만 사용하므로, \(dp\)를 2차원 배열으로 선언하는 대신 1차원 배열으로 선언하여 메모리를 아낄 수 있습니다.

이 경우 시간복잡도는 동일하나 공간복잡도는 \(O(1)\)로 줄어들게 됩니다.

소스코드 (C++)

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
int main() {
    fastio;
    
    int n;
    cin >> n;
    
    int INF = 0x7fffffff;
    
    // 배열을 굉장히 큰 값으로 초기화합니다.
    vector<int> dp(1000, INF);
    dp[0] = 0;
    
    for (int i = 1; i <= n; i++) {
        int next;
        cin >> next;
        
        vector<int> ndp(1000, INF);
        
        // j는 0 ~ 999로 표현되는 각 인덕션의 온도 상태입니다.
        for (int j = 0; j < 1000; j++) {
            if (dp[j] < INF) {
            	// j의 각 자릿수를 구합니다.
                int d1 = j / 100;
                int d2 = (j / 10) % 10;
                int d3 = j % 10;
                
                // 각각의 인덕션에서 버튼을 몇 번 눌러야 하는지 구합니다.
                int dist1 = min((d1 - next + 10) % 10, (next - d1 + 10) % 10);
                int dist2 = min((d2 - next + 10) % 10, (next - d2 + 10) % 10);
                int dist3 = min((d3 - next + 10) % 10, (next - d3 + 10) % 10);
                
                // 인덕션의 다음 온도 상태를 구합니다.
                int i1 = j % 100 + next * 100;
                int i2 = j / 100 * 100 + j % 10 + next * 10;
                int i3 = j / 10 * 10 + next;
                
                // dp값을 업데이트합니다. 이미 더 작은 값이 있다면 업데이트하지 않습니다.
                ndp[i1] = min(ndp[i1], dp[j] + dist1);
                ndp[i2] = min(ndp[i2], dp[j] + dist2);
                ndp[i3] = min(ndp[i3], dp[j] + dist3);
            }
        }
        dp = ndp;
    }
    
    int min_dist = INF;
    for (int i = 0; i < 1000; i++) {
        min_dist = min(min_dist, dp[i]);
    }
    cout << min_dist;
}

문제 링크: https://acmicpc.net/problem/13021 

문제를 요약해봅시다.

• 입력 $L, R$에 대하여 구간 $[L, R]$에 속하는 모든 공을 흰색 또는 검은색으로 칠합니다.
• $M$번의 색칠 후 나올 수 있는 색의 조합의 개수를 구합니다.

어떤 공이 있을 때 이 공을 몇 번 칠하든 반드시 마지막으로 색칠한 것만이 남습니다.

즉, 마지막으로 색칠한 것이 언제 칠한 것인지를 각각의 공에 대해 구해주면 됩니다.

$M$번을 다 칠하고 나면 각 공이 언제 마지막으로 칠해졌는지를 알 수 있습니다. 마지막으로 칠해진 시점이 같은 공들은 반드시 같은 색을 갖게 되므로, 서로 다른 칠해진 시점의 개수를 찾아줍시다.

각 시점마다 총 2가지의 색으로 칠하는 경우가 있으므로, 시점이 $K$개일 때 답은 $2^K$가 됩니다.

정답이 $2^{63} - 1$이하임이 보장된다고 했으므로 비트 시프트 연산으로 간단하게 답을 구할 수 있습니다.

단 64비트 자료형을 사용해야 올바른 답을 얻을 수 있습니다.

시간복잡도는, 총 $M$번 최대 $N$개의 공에 대해 계산을 하는 $O(MN)$의 과정과, 공을 순회하며 서로 다른 시점의 개수를 찾는 $O(N)$의 과정이 있으므로 $O(MN) + O(N) = O(MN)$ 입니다.

소스코드 (C++)

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;

int main() {
    fastio;
    
    int n, k;
    cin >> n >> k;
    
    vector<int> recent_color(n + 1);
    
    for (int i = 1; i <= k; i++) {
        int l, r;
        cin >> l >> r;
        
        for (int j = l; j <= r; j++) {
            recent_color[j] = i;
        }
    }
    
    vector<bool> appeared(n + 1);
    int distincts = 0;
    
    for (int i = 1; i <= n; i++) {
        if (recent_color[i] > 0 && !appeared[recent_color[i]]) {
            appeared[recent_color[i]] = true;
            distincts++;
        }
    }
    
    cout << (1LL << distincts);
    
    return 0;
}

문제 링크: https://acmicpc.net/problem/2482 

문제를 요약해봅시다.

• \(N\)개의 색이 원형으로 배치된 색상환에서 \(K\)개의 색을 골라야 합니다. 이때 \(K\)개의 색은 서로 인접하지 않아야 합니다.
• \(K\)개를 고르는 경우의 수를 계산하고, \(10^9 + 3\)으로 나눈 나머지를 출력합니다.

- 풀이

어떻게 풀어야 할지 감이 잘 안 잡히는 문제입니다.

우선, \(N\)개의 색 중 \(K\)개를 인접하지 않게 고르는 것이 가능한 지부터 따져봅시다. 그러려면 \(N\)개의 색이 있을 때 최대로 고를 수 있는 색의 개수를 구해야 하겠죠.

색을 서로 인접하지 않게 고르려면, 색을 하나 고르고 그 다음 색은 절대 고르지 않는 방법을 취하면 됩니다. 만약 색 \(1\)을 고르면 색 \(2\)는 절대 고르면 안되겠죠!

이런 방법대로 생각해 보면 \(N\)개 색 중에서는 \(\frac{N}{2}\)개 이하인 가장 큰 자연수, 즉 \(\lfloor \frac{N}{2} \rfloor\)개 까지의 색을 고를 수 있음을 알 수 있습니다. 만약 \(K\)가 이보다 크다면 \(0\)을 출력하기만 하면 되겠군요!

- 다이나믹 프로그래밍: \(O(N^3)\)

그러면 이제 일반적인 경우를 생각해 봅시다. 경우의 수를 전부 다 따지는 것은 어렵기 때문에 다이나믹 프로그래밍을 사용합니다.

우선 2차원 배열 \(dp\)를 생각해봅시다. \(dp[i][j]\)는 색을 \(i\)개 사용했을 때 마지막 색의 번호가 \(j\)인 경우의 수라고 하겠습니다.

먼저 색을 1개 사용했을 때의 경우의 수는 전부 1이므로 \(dp[1][x] = 1\)입니다. \((1\leq x\leq N)\)

그리고, 이런 점화식을 이끌어 낼 수 있습니다.

\[dp[i][j] = \sum_{k=1}^{j-2}dp[i-1][k]\]

왜 이런 식을 세울 수 있을까요? 차근차근 따져봅시다.

• \(dp[i][j]\)는 색을 \(i\)개 사용했을 때 마지막 색의 번호가 \(j\)인 경우의 수를 말합니다. 그렇다면 색을 \(i - 1\)개 사용했을 때는 마지막 색이 \(1, 2, ..., j - 3, j - 2\)인 경우를 생각해 볼 수 있습니다.
• 색들 사이에는 공간이 최소 1개만 있으면 되기 때문에 색을 \(i - 1\)개 사용했을 때 마지막 색이 \(1, 2, ..., j - 3, j - 2\)인 경우가 전부 다 가능합니다. 따라서 \(dp[i - 1][1] + dp[i - 1][2] + ... + dp[i - 1][j - 2] = \sum_{k=1}^{j-2}dp[i - 1][k]\)라는 식을 세울 수 있습니다.

이렇게 계산을 반복해서 \(dp[K][x]\)의 값을 전부 구한 뒤 다 더해주기만 하면 됩니다.

하지만 중요한 부분이 있습니다. 색상환은 원 형태이므로 \(dp[K][N]\)의 값을 더할 때는 첫 번째로 고른 색이 색 \(1\)인 경우를 빼줘야 합니다!

마지막 색인 색 \(N\)은 색 \(1\)과 같이 선택하면 안되기 때문입니다. 이를 해결하려면 \(dp[i][j]\)의 값을 다음과 같이 확장해주면 됩니다.

\[dp[i][j] = (첫 색이  1인 경우, 첫 색이  1이 아닌 경우)\]

계산을 할 때 두 경우를 나눠서 더해주면 마지막에 \(dp[K][N]\)을 더할 때 색 \(1\)로 시작한 경우의 수를 뺄 수 있습니다.

여기까지 했다면 답은 올바르게 나옵니다. 시간복잡도를 계산해보면, \(dp[i][j]\)를 \(O(KN)\)번 계산해야 하고, 각 계산마다 \O(K)\)번의 덧셈을 사용하므로 총 시간복잡도는 \(O(NK^2) = O(N^3)\)입니다.

\(N\leq1000\)이므로 \(O(N^3)\)의 시간복잡도로는 시간 안에 문제를 해결할 수 없습니다. 어떻게 최적화하면 좋을까요?

- 최적화: \(O(N^2)\)

점화식 \(dp[i][j] = \sum_{k=1}^{j-2}dp[i -1][k]\)를 계산하는 과정을 살펴봅시다. 잘 보면 다음이 성립합니다.

\[dp[i][j + 1] = \sum_{k=1}^{j-1}dp[i-1][k] = \sum_{k=1}^{j-2}dp[i-1][k] + dp[i-1][j-1] = dp[i][j] + dp[i - 1][j - 1]\]

즉, 각각의 \(dp[i][j]\)를 계산할 때마다 \(j-2\)번의 반복을 할 필요가 없습니다! 점화식을 더 간단하게 만들 수 있습니다.

\[dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 2]\]

이때의 시간복잡도는 \(O(KN) = O(N^2)\)입니다.

추가로, 점화식을 잘 살펴보면 \(dp[i][j]\)를 계산할 때 \(dp[i][j - 1]\)과 \(dp[i - 1][j - 2]\)만이 필요한 것을 알 수 있습니다.

즉 \(dp[i - 2], dp[i - 3], ...\)은 계산에 필요하지 않습니다!

따라서, \(dp\) 배열을 2차원으로 선언하는 대신, 1차원 배열로 선언하여 메모리 사용량을 더 줄일 수 있습니다.

여담으로, 이 문제는 조합론으로도 풀 수 있습니다. 고등학교 수학에서 나오는 어려운 경우의 수 문제입니다.

색 \(K\)개를 반드시 골라야 하니 \(K\)개의 물건이 있다고 가정하고, 그 사이에 빈칸(선택하지 않는 색)을 끼워넣는 경우의 수를 고르는 것입니다.

구체적인 접근법은 다음과 같습니다.

• 문제에서 \(K\)개의 색은 이미 골라졌다고 생각하고, \(K\)개의 선택하지 않은 색을 각 색의 뒤에 배치했다고 생각해봅시다.
• 남은 색은 \(N - 2K\)개이고, 이를 배치할 수 있는 공간은 \(K\)개 색들 사이의 총 \(K\)개 공간입니다.
• \(N - 2K\)개의 색을 \(K\)개 공간에 배치할 수 있는 경우의 수를 계산하면 됩니다.

단 계산이 조금 까다로울 수 있다고 생각합니다. 색 \(N - 2K\)개를 \(K\)개 이하로 나누는 문제가 되므로 자연수의 분할을 생각해보세요.

마지막으로 어떤 방식으로 문제를 풀든 32비트 정수형은 오버플로우가 일어날 수 있다는 사실을 잊지 말도록 합시다.

소스코드 (C++, 다이나믹 프로그래밍)

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;

constexpr ll mod = 1e9 + 3;

class Node {
public:
    // 색 1로 시작하는 경우의 수
    ll z = 0;
    // 색 1로 시작하지 않는 경우의 수
    ll nz = 0;
    
    Node() {}
    Node(ll z, ll nz) {
        this->z = z;
        this->nz = nz;
    }
    
    Node operator+(const Node &n) const {
        return Node((this->z + n.z) % mod, (this->nz + n.nz) % mod);
    }
};

int main() {
    fastio;
    
    int n, k;
    cin >> n >> k;
    
    if (k > n / 2) {
        cout << 0;
        return 0;
    }
    
    vector<Node> dp(n, Node(0, 1));
    dp[0] = Node(1, 0);
    
    // 이전 값을 이용해 점화식을 계산합니다.
    for (int i = 1; i < k; i++) {
        vector<Node> next_dp(n);
        
        for (int j = 2; j < n; j++) {
            next_dp[j] = next_dp[j - 1] + dp[j - 2];
        }
        
        dp = next_dp;
    }
    
    // 첫 색과 마지막 색을 동시에 고르는 경우의 수를 제외합니다.
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (i < n - 1) {
            ans += dp[i].z;
            ans %= mod;
        }
        ans += dp[i].nz;
        ans %= mod;
    }
    cout << ans;
    
    return 0;
}