취미로 코딩하기

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

이번에 볼 문제는 백준 22412번 문제인 ABC Gene이다.
문제는 아래 링크를 확인하자.

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

문자열 "ABC"에 주어진 규칙대로 변화를 1회 이상 주어 얻은 어떤 문자열을 S라 하자. 이 때, S의 이전 단계는 무엇인지 역추적할 수 있을까?

S의 부분문자열로 "ABC"가 존재하지 않는다면 어떤 변화로도 해당 문자열을 얻을 수 없을 것이다. 따라서 S는 부분문자열로 "ABC"를 적어도 하나 포함해야 한다. 한편, 모든 부분문자열 "ABC"는 이전 단계에서 바뀐 결과물이라는 점도 관찰할 수 있다. 이전 단계에서 어떤 문자를 ABC로 바꿔서 기존 문자와 연결된 새로운 "ABC"를 얻을 수는 없으며, 이전 단계에 있던 것이 그대로 오는 것도 불가능(어떤 연산을 해도 A나 B나 C가 있으므로 변화가 생김)하기 때문이다.

또한 이 "ABC"들이 어떤 문자였는지는 해당 문자열의 남은 다른 문자들 중 없는 문자가 되어야 한다는 점도 관찰하자. 이 때 남은 다른 문자가 0, 1, 3종류이면 불가능함을 확인하자.

위 관찰을 활용하여 주어진 문자열을 역추적해 문제를 해결하자.

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

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

string s, ss;

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

    cin >> s;

    while (s != "ABC") {
        bool chk = 0;
        ss.clear();
        for (auto &l:s) {
            ss += l;
            if (ss.length() > 2 && ss.substr(ss.length() - 3, 3) == "ABC") {
                ss.pop_back();
                ss.pop_back();
                ss.pop_back();
                ss += 'D';
                chk = 1;
            }
        }
        if (!chk) break;
        bool chkA = 0, chkB = 0, chkC = 0;
        for (auto &l:ss) {
            if (l == 'A') chkA = 1;
            else if (l == 'B') chkB = 1;
            else if (l == 'C') chkC = 1;
        }
        if (chkA && chkB && chkC) break;
        if (chkA && chkB) {
            for (auto &l:ss) {
                if (l == 'D') l = 'C';
            }
        }
        else if (chkB && chkC) {
            for (auto &l:ss) {
                if (l == 'D') l = 'A';
            }
        }
        else if (chkC && chkA) {
            for (auto &l:ss) {
                if (l == 'D') l = 'B';
            }
        }
        else break;
        swap(s, ss);
    }

    if (s == "ABC") cout << "Yes";
    else cout << "No";
}

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

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

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

어떤 음이 아닌 정수 \(a\)에 대하여 이 수와 xor연산을 해 \(K\)가 되는 수는 두 수의 xor뿐임을 관찰하자.

\(K\)는 0이 아니므로, 위 관찰을 이용하면 어떤 한 정수를 수열에 넣고 해당 수와 \(k\)의 xor을 이후에 넣지 않는 것을 반복하는 방식으로 수열을 구성해 문제를 해결할 수 있다.

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

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

int N, M, K;
bool visited[400001];
vector<int> ans;

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

    cin >> N >> M >> K; ans.reserve(N);
    for (int i = 1; i <= M && ans.size() < N; i++) {
        if (visited[i]) continue;
        if ((i ^ K) < 400001) visited[i ^ K] = 1;
        ans.emplace_back(i);
    }
    if (ans.size() < N) cout << -1;
    else {
        for (auto &x:ans) cout << x << ' ';
    }
}

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

이번에 볼 문제는 백준 6913번 문제인 Constrained Permutation이다.
문제는 아래 링크를 확인하자.

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

주어지는 나열 순서를 모두 만족하는 순열의 개수를 구하는 문제이다.

글쓴이는 위상정렬과 같은 원리로 앞서 와야 하는 수가 모두 등장한 경우에만 해당 수를 순열에 등장시키는 방식으로 문제를 해결하였다.

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

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

int N, K;
int deg[10];
vector<int> G[10];
bool visited[10];
int ans;
vector<int> vec;
void src(int cur, int lv) {
    if (lv == N) {
        ans++;
        return;
    }
    for (auto &x:G[cur]) {
        deg[x]--;
        if (!deg[x]) vec.emplace_back(x);
    }
    for (auto &nxt:vec) {
        if (!visited[nxt]) visited[nxt] = 1, src(nxt, lv + 1), visited[nxt] = 0;
    }
    for (auto &x:G[cur]) {
        if (!deg[x]) vec.pop_back();
        deg[x]++;
    }
}

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

    vec.reserve(10);
    cin >> N >> K;
    while (K--) {
        int x, y; cin >> x >> y;
        G[x].emplace_back(y), deg[y]++;
    }
    
    for (int i = 1; i <= N; i++) {
        if (!deg[i]) vec.emplace_back(i);
    }
    src(0, 0);
    cout << ans;
}

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

이번에 볼 문제는 백준 18270번 문제인 Livestock Lineup이다.
문제는 아래 링크를 확인하자.

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

주어진 8마리 소의 나열의 경우의 수는 8팩토리얼, 즉 40320가지가 있다.

40320은 충분히 작은 수이므로, 주어진 이름의 순열을 사전순으로 둘러보면서 모든 조건을 만족하는 순열을 찾는 것으로 문제를 해결할 수 있다.

사전순 다음 순열을 구하는 알고리즘을 모르더라도 next_permutation 함수를 이용하여 구현을 쉽게 할 수 있다. 또는 사전순과 관계 없이 모든 순열에 대하여 조사를 한 뒤 그 중 사전순으로 가장 빠른 순열을 고르는 것으로도 문제를 해결할 수 있다.

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

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

int N;
string X[7][2];
string s[8] = {"Bessie", "Buttercup", "Belinda", "Beatrice", "Bella", "Blue", "Betsy", "Sue"};
string tmp;

bool chk() {
    for (int i = 0; i < N; i++) {
        bool tmp = 0;
        for (int k = 0; k < 7; k++) {
            if (X[i][0] == s[k] && X[i][1] == s[k + 1]) tmp = 1;
            else if (X[i][0] == s[k + 1] && X[i][1] == s[k]) tmp = 1;
        }
        if (!tmp) return 0;
    }
    return 1;
}

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

    cin >> N;
    for (int i = 0; i < N; i++) cin >> X[i][0] >> tmp >> tmp >> tmp >> tmp >> X[i][1];
    sort(s, s + 8);
    while (!chk()) next_permutation(s, s + 8);
    for (int i = 0; i < 8; i++) cout << s[i] << '\n';
}

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

이번에 볼 문제는 백준 3870번 문제인 Find the Multiples이다.
문제는 아래 링크를 확인하자.

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

\(Q\)가 2 또는 5인 경우 각 자리수만 보고도 문제를 쉽게 해결할 수 있다. 그 외의 경우를 생각해 보자.

주어진 수의 임의의 substring으로 구성된 수는 0을 적절히 붙여 (해당 부분부터 끝까지 쓴 수에서 뒤에 덧붙인 수를 뺀 수)로 만들 수 있다. 한편, \(Q\)는 2나 5가 아니므로 10에는 \(Q\)의 소인수가 없고, 따라서 0을 뒤에 덧붙이거나 지워도 \(Q\)의 배수 여부는 변하지 않는다. 따라서 각 자리부터 시작하는 접미사의 형태로 이루어진 문자열의 집합을 이용해 문제를 해결할 수 있을 것임을 관찰할 수 있다.

문제 조건에 따라 0으로 시작하는 수는 고려하지 않는다는 점에 유의하자.

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

//3870
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;

ll N, S, W, Q, ans;
ll AA[100001];
ll A[100001];
map<int, int> mp;

void solve2() {
    int cnt0 = 0, cnt1 = 0;
    for (int i = 0; i < N; i++) {
        if (A[i] & 1) cnt1++;
        else {
            ans += cnt0 + cnt1;
            if (A[i]) cnt0++, ans++;
        }
    }
    cout << ans << '\n';
}

void solve5() {
    int cnt0 = 0, cnt1 = 0;
    for (int i = 0; i < N; i++) {
        if (A[i] % 5) cnt1++;
        else {
            ans += cnt0 + cnt1;
            if (A[i]) cnt0++, ans++;
        }
    }
    cout << ans << '\n';
}

void solve() {
    ans = 0;
    for (int i = 0; i < N; i++) {
        AA[i] = A[i] = (S / 7) % 10;
        if (S & 1) S = (S >> 1) ^ W;
        else S >>= 1;
    }

    //2와 5 예외처리
    if (Q == 2) {
        solve2();
        return;
    }
    else if (Q == 5) {
        solve5();
        return;
    }

    A[N] = 0;

    for (ll i = N - 1, d = 1; i > -1; i--, d = d * 10 % Q) {
        A[i] = (A[i + 1] + d * A[i]) % Q;
    }

    mp.clear();
    for (ll i = 0; i < N; i++) {
        ans += mp[A[i]];
        if (AA[i]) mp[A[i]]++;
    }
    ans += mp[0];
    
    cout << ans << '\n';
}

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

    cin >> N >> S >> W >> Q;
    while (N) solve(), cin >> N >> S >> W >> Q;
}

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

이번에 볼 문제는 백준 33172번 문제인 周期文字列 (Cycle String)이다.
문제는 아래 링크를 확인하자.

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

주어지는 문자열의 길이가 짧다는 점을 눈여겨보자. 문자열의 주기는 첫 문자를 항상 포함해야 한다는 점을 관찰하자.

따라서 주어진 문자열의 앞 \(k\)글자로 이루어진 문자열을 주기로 하는 문자열을 생성한 뒤 원래 문자열과 같아지는지를 일일이 확인하는 것으로 문제를 해결할 수 있다. 단, \(k\)는 전체 문자열의 길이의 (자기자신이 아닌) 약수이다.

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

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

int N;
string s, ss;

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

    cin >> N >> s;
    for (int i = 1; i < N; i++) {
        if (N % i) continue;
        string tmp = s.substr(0, i); ss.clear();
        while (ss.length() < s.length()) ss += tmp;
        if (s == ss) {
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
}