취미로 코딩하기

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

이번에 볼 문제는 백준 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();
}

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

이번에 볼 문제는 백준 14970번 문제인 Almost Identical Programs이다.
문제는 아래 링크를 확인하자.

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

주어진 두 문자열이 같으면 IDENTICAL을 출력하면 된다는 점을 확인하자. 아래에서는 두 문자열이 다른 경우만을 생각한다.

따옴표의 개수가 같지 않다면 둘은 같을 수가 없다는 점을 관찰하자. 또한 따옴표의 개수가 같은 경우, (올바른 순서를 구성하는) 두 따옴표 사이에 포함된 문자열의 쌍 중 한 쌍만 다른 경우만 답이 CLOSE가 됨을 관찰하자.

위 관찰을 그대로 구현해 문제를 해결할 수 있다.

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

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

string s1, s2, ss1, ss2, tmp;
vector<string> v1, v2;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    while (getline(cin, s1) && getline(cin, s2)) {
        if (s1 == s2) cout << "IDENTICAL\n";
        else {
            ss1.clear(), ss2.clear(), v1.clear(), v2.clear();
            int sgn = 0;
            tmp.clear();
            for (auto &l:s1) {
                if (l == '\"') {
                    sgn ^= 1;
                    if (!sgn) v1.emplace_back(tmp), tmp.clear();
                    ss1 += '\"';
                }
                else if (sgn) tmp += l;
                else ss1 += l;
            }
            sgn = 0;
            tmp.clear();
            for (auto &l:s2) {
                if (l == '\"') {
                    sgn ^= 1;
                    if (!sgn) v2.emplace_back(tmp), tmp.clear();
                    ss2 += '\"';
                }
                else if (sgn) tmp += l;
                else ss2 += l;
            }
            if (ss1 != ss2 || v1.size() != v2.size()) cout << "DIFFERENT\n";
            else {
                int cnt = 0, vsize = v1.size();
                for (int i = 0; i < vsize; i++) {
                    if (v1[i] != v2[i]) cnt++;
                }
                if (cnt > 1) cout << "DIFFERENT\n";
                else cout << "CLOSE\n";
            }
        }
    }
}

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

이번에 볼 문제는 백준 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;
}