취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 6588번 문제인 골드바흐의 추측이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/6588

골드바흐의 추측은 지금까지 해결되지 않는 정수론의 추측 중 하나로, 그 명제의 단순함에 지금까지 많은 사람들이 증명을 시도해온 문제이다.

단지 지금까지 알려져 있는 내용은 상당히 큰 수까지 이 골드바흐의 추측이 성립한다는 것 뿐이다.

물론, 문제에서 주어진 범위인 100만 이하의 수에서는 당연히 이 추측이 성립한다.

따라서, 문제의 조건 중 추측이 틀렸다는 것을 출력하는 부분은 구현할 필요가 없다.

한번에 계산해야 할 테스트케이스가 많으므로, 에라토스테네스의 체(Sieve of Eratosthenes)를 이용하여 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin; using std::cout;

bool sieve[1000001];

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 2;i <= 1000;i++) {
        if (sieve[i] == 0) {
            for (int j = i * i;j <= 1000000;j += i) sieve[j] = 1;
        }
    }
    int N; cin >> N;
    while (N!=0) {
        for (int i = 3;i <= 1000;i++) {
            if (!sieve[i] and !sieve[N - i]) {
                cout << N << " = " << i << " + " << N - i << '\n'; break;
            }
        }
        cin >> N;
    }
    return 0;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16922번 문제인 로마 숫자 만들기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/16922

이 문제에서는 정확히 총 N개의 I, V, X, L을 이용하여 각 로마숫자가 나타내는 수의 총합의 가짓수를 구하는 문제이다.

N개의 문자를 전부 이용해야 하고, N의 범위가 20까지이므로, 백트래킹을 이용해 전체를 탐색해도 충분히 풀 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin; using std::cout;

bool chk[1001];
int cnt = 0;

void L(int N, int sum) {
    if (!chk[sum + 50 * N]) {
        chk[sum + 50 * N] = 1;
        cnt++;
    }
}

void X(int N, int sum) {
    for (int i = 0;i <= N;i++) {
        L(N - i, sum + 10 * i);
    }
}

void V(int N, int sum) {
    for (int i = 0;i <= N;i++) {
        X(N - i, sum + 5 * i);
    }
}

void I(int N) {
    for (int i = 0;i <= N;i++) {
        V(N - i, i);
    }
}

int main()
{
    int N; cin >> N; I(N); cout << cnt; return 0;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16969번 문제인 차량 번호판 2이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/16969

이 문제는 경우의 수를 계산하는 문제이다.

숫자 또는 문자가 연속으로 올 경우, 그 연속된 부분문자열의 2번째부터는 전체 가능한 문자에서 바로 이전에 온 문자가 올 수 없으니 1을 뺀 값을 곱해야한다는 점을 신경쓰자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using std::cin; using std::cout;
using std::string;

int main()
{
    string s; cin >> s;
    int slen = s.length();
    long long ans = 1;
    char before = 'a';
    for (int i = 0;i < slen;i++) {
        if (s[i] == 'c') {
            ans *= (before == 'c') ? 25 : 26;
            before = 'c';
        }
        if (s[i] == 'd') {
            ans *= (before == 'd') ? 9 : 10;
            before = 'd';
        }
        ans %= 1000000009;
    }
    cout << ans;
    
    return 0;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1948번 문제인 임계경로이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1948

글쓴이는 이 문제를 위상정렬(topological sorting)으로 도착도시까지 찾아가면서 각 도시까지 걸리는 최대시간으로 가는 경로가 되는 도시들을 저장한 후, 도착도시에서 출발도시방향으로 역추적하며 간선의 수를 세어 풀었다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using std::cin; using std::cout;
using std::vector;
using std::pair;

vector<pair<int,int>> G[10001]; // 출발도시에서 도착도시로 가는 가중치 있는 그래프
int inway[10001]; // i번 노드로 들어오는 경로수(indegree)
int dist[10001]; // i번 노드까지 오는 데에 걸리는 최대 시간
vector<int> cnt[10001]; // i번 노드로 들어오는 데에 최대 시간이 걸리는 경로인 이전노드들을 모은 그래프
int target; // 도착도시
bool visited[10001]; // backtrack에서 이미 확인한 도시 중복탐색 방지용
int running = 0; // 달려야하는 도로 수

void backtrack(int node) {
    vector<int>::iterator iter = cnt[node].begin();
    for (;iter != cnt[node].end();iter++) {
        running++;
        if (!visited[*iter]) {
            visited[*iter] = 1;
            backtrack(*iter);
        }
    }
}

void dfs(int root, int parent) {
    if (root == target) {
        backtrack(target);
        cout << dist[target] << '\n' << running;
    }
    vector<pair<int, int>>::iterator iter = G[root].begin();
    for (;iter != G[root].end();iter++) {
        int current = (*iter).first, l = (*iter).second;
        inway[current]--;
        if (dist[current] < dist[root] + l) {
            dist[current] = dist[root] + l;
            cnt[current].clear();
            cnt[current].push_back(root);
        }
        else if (dist[current] == dist[root] + l) {
            cnt[current].push_back(root);
        }
        if (inway[current] == 0) dfs(current, root);
    }
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;
    for (int i = 0;i < m;i++) {
        int s, e, t; cin >> s >> e >> t;
        G[s].push_back({e,t});
        inway[e]++;
    }
    
    int root;
    cin >> root >> target;
    dfs(root, 0);

    return 0;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 6549번 문제인 히스토그램에서 가장 큰 직사각형이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/6549

이 문제는 크게 두가지 방법으로 풀 수 있음이 알려져있다. 하나는 분할정복(divide&conquer)이고, 다른 하나는 스택을 이용한 풀이방법이다.

글쓴이는 스택을 이용하여 풀어보았다.

가장 큰 직사각형은 그 직사각형의 좌우 막대가 직사각형의 높이보다 낮거나 그 쪽으로 더 이상 막대가 없어야하고, 그 직사각형을 구성하는 막대 중 현재 직사각형의 높이와 같은 높이인 막대가 있어야 한다.

따라서, 스택을 왼쪽의 막대서부터 읽으면서, (같거나) 높아지는 순으로 막대가 들어있게 관리하면 문제를 간단히 풀 수 있다.

아래는 글쓴이가 문제를 풀기 위해 사용한 코드의 설명이다.

pair<long long,long long>형을 저장하는 스택을 만들고, {0,0}을 저장해두자.

이 pair의 first값은 그 막대의 높이, second값은 그 막대의 가로길이를 의미한다.

매 밑변이 1인 직사각형의 높이를 입력받을 때마다 현재 스택의 가장 위에 놓여있는 막대보다 길이가 크거나 같다면 {막대높이, 1}을 스택에 밀어넣는다.

그렇지 않다면, 스택에서 입력받은 높이보다 높은 막대를 빼면서, 만나는 막대의 높이와 그 막대까지의 가로를 계산해 현재까지의 최대 넓이를 갱신한다. 스택에서 더 빼낼 막대가 없다면, 스택에 {입력받은 막대 높이, 빼낸 막대 가로 총합+1}을 집어넣는다.

이를 반복하면 답을 구할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using std::cin; using std::cout;
using std::vector;
using std::pair;

void solve(int N) {
    long long ans = 0;
    vector<pair<long long, long long>> stk = { {0,0} };
    for (int i = 0;i < N;i++) {
        long long current; cin >> current;
        if (current >= stk.back().first) stk.push_back({ current,1 });
        else {
            long long cnt = 0;
            while (current < stk.back().first) {
                long long height, width;
                height = stk.back().first;
                width = stk.back().second; stk.pop_back();
                cnt += width;
                if (ans < height * cnt) ans = height * cnt;
            }
            stk.push_back({ current,cnt + 1 });
        }
    }
    long long cnt = 0;
    while (0 < stk.back().first) {
        long long height, width;
        height = stk.back().first;
        width = stk.back().second; stk.pop_back();
        cnt += width;
        if (ans < height * cnt) ans = height * cnt;
    }
    cout << ans << '\n';
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    while (N!=0) {
        solve(N);
        cin >> N;
    }
    
    return 0;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1693번 문제인 트리 색칠하기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1693

이 문제에서는 인접한 노드에 다른 색을 칠하면서 사용한 비용이 최소가 되게 트리의 노드를 색칠해야 한다.

이 문제를 풀기 위해 가장 먼저 생각해야할 것은 "최대 몇 개의 색이 필요할 것인가"이다.

문제에 나와있는 것과 같이 N개의 노드에 N가지 색을 칠하는 경우를 모두 조사하려면 시간과 메모리가 불필요하게 많이 들기 때문이다.

다음과 같은 관찰을 하자.

1) 색을 한 종류 사용하여 최소비용인 경우가 등장하는 트리는 최소 1개 노드, 2개를 사용하여 최소비용인 경우가 등장하는 트리는 최소 2개의 노드가 있어야 한다.

2) 함수 f(n)을 "색을 n 종류 사용하여 최소비용인 경우가 등장하는 트리가 가지고 있어야 할 최소 개수의 노드"로 정의하자. 1에 의햐여 f(1) = 1, f(2) = 2 이다.

3) f(i)는 f(i-1)+f(i-2)+...+f(2)+f(1) 보다 크거나 같다. 그 트리를 i가지 색으로 칠하는 것이 최소비용이라면 비용이 i인 색을 다른 색으로 바꿀 수 없어야 하고, 그렇다면 i번째 색을 칠해야하는 노드에는 i-1, i-2, ..., 2, 1의 비용이 들어가는 색을 가진 노드가 각각 인접해있어야 하기 때문이다.

4) 2, 3의 관계식을 이용하면 f(i)는 2^(i-2)보다 크거나 같음을 알 수 있다.

4의 관계식에 따라, 이 문제의 범위(노드 10만개)에서는 색을 많아야 18가지만 사용할 것이라는 것을 알 수 있다. 실제로 18개보다 더 적은 색만을 이용할 가능성도 있기는 하지만(정확한 bound가 아니므로), 이 정도로 범위를 축소한 것 만드로도 문제를 푸는 데에는 충분하다.

남은 것은, 리프노드서부터 각 노드를 i(1 이상 18이하)로 칠할 때 그 노드를 루트로 하는 부분트리를 칠하는 최소비용을 기록해나가는 것이다.

탐색을 마치면, 루트로 정한 노드를 살펴 각 색깔별로 칠해져있는 경우의 최소비용들 가운데 최솟값을 출력하면 된다. 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using std::cin; using std::cout;
using std::vector;

int arr[100001][19]; // arr[i][j]: j색으로 칠한 i번 노드를 루트로 갖는 부분트리의 비용최솟값
vector<int> G[100001];

void dfs(int root, int parent) {
    vector<int>::iterator iter = G[root].begin();
    for (;iter != G[root].end();iter++) {
        if (*iter == parent) continue;
        dfs(*iter, root);

        int s1, s2;// s1: 가장 작은 것, i1: s1의 index, s2: 두번째로 작은 것
        int i1;
        if (arr[*iter][1] < arr[*iter][2]) {
            s1 = arr[*iter][1], i1 = 1, s2 = arr[*iter][2];
        }
        else s1 = arr[*iter][2], i1 = 2, s2 = arr[*iter][1];
        for (int i = 3;i < 19;i++) {
            if (arr[*iter][i] <= s1) {
                s2 = s1;s1 = arr[*iter][i];
                i1 = i;
            }
            else if (arr[*iter][i] < s2) {
                s2 = arr[*iter][i];
            }
        }
        for (int i = 1;i < 19;i++) {
            if (i != i1) arr[root][i] += s1;
            else arr[root][i] += s2;
        }
    }
}


int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    for (int i = 1;i <= N;i++) { // arr 초기화: 각 j번째 성분은 그 노드를 j색으로 칠하므로
        for (int j = 1;j <= 18;j++) {
            arr[i][j] = j;
        }
    }
    for (int i = 1;i < N;i++) {
        int x, y; cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1, 0);
    int ans = arr[1][1];
    for (int j = 2;j <= 18;j++) {
        if (ans > arr[1][j]) ans = arr[1][j];
    }
    cout << ans;

    return 0;
}