취미로 코딩하기

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

이번에 볼 문제는 백준 24605번 문제인 Tetris Generation이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/24605

7-bag 시스템이 적용된 테트리스에서 주어진 순서대로 테트리스 블록이 생성될 수 있는지 확인하는 문제이다.

가능한 각각의 새 bag의 시작점(많아야 7가지)에 대하여 각 bag에 겹치는 블록이 들어있는지 판단해 문제를 해결하자. 이를 구현할 때, 첫 bag과 마지막 bag에는 7개보다 적은 블록이 들어있을 수도 있다는 점에 유의하자.

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

#include <iostream>
#include <cstring>
using namespace std;

int N;
string s;
int visited[128];

void solve() {
    int ans = 0;
    cin >> s; N = s.length();
    for (int L = 0; L < 7; L++) {
        bool cchk = 1;
        memset(visited, 0, sizeof(visited));
        for (int i = 0; i < min(L, N); i++) {
            if (visited[s[i]]) cchk = 0;
            visited[s[i]] = 1;
        }
        for (int k = L; k < N; k += 7) {
            memset(visited, 0, sizeof(visited));
            for (int i = k; i < min(k + 7, N); i++) {
                if (visited[s[i]]) cchk = 0;
                visited[s[i]] = 1;
            }
        }

        if (cchk) ans = 1;
    }
    cout << ans << '\n';
}

int T;

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

    cin >> T;
    while (T--) solve();
}

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

이번에 볼 문제는 백준 29279번 문제인 Поломка Бамблби이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/29279

쿼리로 주어진 범위에 1이 아닌 수가 포함되어 있다면 그 수 하나만 포함된 구간의 mex값은 1이 되고, 따라서 gcd는 항상 1이 된다.

한편, 쿼리로 주어진 범위에 1만 포함되어 있다면 모든 구간의 mex값이 2가 되고, 따라서 gcd는 항상 2가 된다.

주어진 범위에 1이 아닌 수가 포함되어있는지 여부는 각 배열의 성분을 1인 경우와 아닌 경우 각각 0과 1을 부여한 배열의 누적 합을 계산해 두는 것으로 빠르게 판별할 수 있다.

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

#include <iostream>
using namespace std;

int N, Q;
int A[100001];

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

    cin >> N;
    for (int i = 1; i <= N; i++) {
        int x; cin >> x;
        if (x == 1) A[i] = A[i - 1];
        else A[i] = A[i - 1] + 1;
    }
    cin >> Q;
    while (Q--) {
        int L, R; cin >> L >> R;
        if (A[R] - A[L - 1]) cout << 1 << '\n';
        else cout << 2 << '\n';
    }
}

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

이번에 볼 문제는 백준 7803번 문제인 Burger, French Fries, Soft Drink이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/7803

먼저 주어진 B, F, S의 개수가 서로 같지 않다면 당연히 세트를 나누는 것이 불가능하다. 아래에서는 전체 B, F, S의 개수가 서로 같은 상황만을 생각하자.

앞의 B, F, S의 개수가 서로 같게 끊을 수 있는 모든 위치를 먼저 구하면, 세트를 나눌 수 있는 지점은 그 부분뿐이며 그 중 \(N-1\)개의 지점을 고르는 것으로 모든 가능한 경우를 찾을 수 있다.

이와 같은 경우의 수는 조합과 같으므로, 파스칼의 삼각형을 구현해 문제를 해결할 수 있다. 문제의 답의 최댓값이 충분히 작아 이와 같은 방식으로도 문제를 충분히 해결할 수 있다.

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

#include <iostream>
#include <string>
using namespace std;

int comb[34][34];
void combinit() {
    comb[0][0] = 1;
    for (int n = 1; n < 34; n++) {
        comb[n][0] = 1;
        for (int r = 1; r < 34; r++) {
            comb[n][r] = comb[n - 1][r - 1] + comb[n - 1][r];
        }
    }
}

int N; string s;
int cnt[128];

void solve() {
    int n = 0;
    cnt['B'] = cnt['F'] = cnt['S'] = 0;
    for (auto &l:s) {
        cnt[l]++;
        if (cnt['B'] == cnt['F'] && cnt['F'] == cnt['S']) n++;
    }
    if (cnt['B'] != cnt['F'] || cnt['F'] != cnt['S']) {
        cout << "Impossible\n";
        return;
    }
    n--;

    if (comb[n][N - 1]) cout << comb[n][N - 1] << '\n';
    else cout << "Impossible\n";
}

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

    combinit();
    while (cin >> N >> s) solve();
}

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

이번에 볼 문제는 백준 7352번 문제인 Mini-Tetris 3023이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/30570

S-tile을 이용하면서 2행의 직사각형 형태를 채우려면 적어도 2개의 Corner 타일이 필요하다는 점을 관찰하자. 또한 2개의 Corner 타일이 있기만 해도 그 사이에 모든 S-tile을 이용할 수 있다는 점을 관찰하자.

위 관찰을 이용하면 (1)먼저 S-tile을 사용할 수 있다면 전부 사용하고 (2) 남은 Square 타일과 Corner 타일로 최대한 직사각형을 길게 채우는 것으로 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

int A, B, C, ans;

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

    cin >> A >> B >> C;
    if (C > 1) {
        ans += B * 2 + 3;
        C -= 2;
    }
    ans += A * 2;
    ans += C / 2 * 3;
    cout << ans;
}

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

이번에 볼 문제는 백준 7352번 문제인 Рыцарский щит이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/20490

원하는 길이를 최소화하는 것은 두 삼각형의 맞닿은 길이를 최대화하는 것과 같다는 점을 관찰하자.

두 삼각형이 맞닿은 변의 길이를 최대화하려면 각 삼각형의 가장 긴 변을 최대한 붙이면 된다. 이 때 맞닿은 길이는 두 변 중 더 짧은 거리가 된다.

따라서 문제의 답은 여섯 변의 길이의 합에서 주어진 각각의 두 삼각형의 가장 긴 변의 길이 중 더 작은 값을 두 번 뺀 값이 된다.

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

#include <iostream>
using namespace std;

int A, B, C, X, Y, Z, P, Q;

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

    cin >> A >> B >> C >> X >> Y >> Z;
    P = max(A, max(B, C)), Q = max(X, max(Y, Z));
    cout << A + B + C + X + Y + Z - min(P, Q) * 2;
}

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

이번에 볼 문제는 백준 7352번 문제인 Sorting it All Out이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/7352

각 수를 정점으로, 대소관계를 방향에지로 모델링하면, 주어진 그래프가 문제의 조건을 만족하는 시점은 그래프가 (1) DAG이고 (2) 최장거리가 \(n\)이 되는 경우이며, 중간에 탐색이 끝나는 시점은 (1) 앞선 조건을 만족하는 순간이 오거나 (2) DAG가 아니게 되는 경우이다.

DAG 여부를 알아내는 것은 주어진 그래프에 사이클이 있는지 판정하는 것으로 할 수 있다. 또한 DAG의 최장거리는 위상정렬순으로 정점을 탐색하는 것으로 구할 수 있다. 이 두 알고리즘을 잘 구현하여 문제를 해결하자. 주어질 수 있는 노드의 수가 매우 적으므로, 매 탐색단계마다 위 과정을 매번 수행하는 것으로도 문제를 충분히 해결할 수 있다.

한 테스트케이스의 과정 중간에서 DAG가 아니게 되었다는 정보를 알아냈어도 그 테스트케이스에서 주어지는 모든 대소관계를 읽을 필요가 있다는 점에 유의하자.

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

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

int N, M;
vector<char> G[128];
pair<char, char> E[1000];

char par[128], lst;
int indeg[128], dist[128];
queue<int> que;

void func() {
    lst = 0;
    memset(par, 0, sizeof(par));
    memset(indeg, 0, sizeof(indeg));
    for (int i = 0; i < N; i++) {
        char x = 'A' + i;
        for (auto &y:G[x]) indeg[y]++;
    }
    memset(dist, 0, sizeof(dist));
    for (int i = 0; i < N; i++) {
        char x = 'A' + i;
        if (!indeg[x]) dist[x] = 1, que.push(x);
    }
    while (!que.empty()) {
        char cur = que.front(); que.pop();
        lst = cur;
        for (auto &nxt:G[cur]) {
            indeg[nxt]--;
            if (!indeg[nxt]) dist[nxt] = dist[cur] + 1, par[nxt] = cur, que.push(nxt);
        }
    }
}

void solve() {
    for (int m = 0; m < M; m++) {
        cin >> E[m].first >> E[m].second >> E[m].second;
    }
    for (char c = 'A'; c <= 'Z'; c++) G[c].clear();
    for (int k = 0; k < M; k++) {
        G[E[k].first].emplace_back(E[k].second);
        func();
        if (dist[lst] == N) {
            cout << "Sorted sequence determined after " << k + 1 << " relations: ";
            string ans = "";
            while (lst) {
                ans += lst;
                lst = par[lst];
            }
            while (!ans.empty()) {
                cout << ans.back();
                ans.pop_back();
            }
            cout << ".\n";
            return;
        }
        for (int i = 0; i < N; i++) {
            char x = 'A' + i;
            if (indeg[x]) {
                cout << "Inconsistency found after " << k + 1 << " relations.\n";
                return;
            }
        }
    }
    cout << "Sorted sequence cannot be determined.\n";
}

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

    cin >> N >> M;
    while (N) {
        solve();
        cin >> N >> M;
    }
}