취미로 코딩하기

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

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

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

이번에 볼 문제는 백준 33171번 문제인 いずれか片方 (Either, but Not Both)이다.
문제는 아래 링크를 확인하자.

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

\(N\) 이하의 양의 정수 중 \(A\)와 \(B\) 두 수 모두로 나누어떨어지지는 않지만 어떤 하나의 수로는 나누어떨어지는 수의 개수를 구하는 문제이다.

주어지는 \(N\)의 범위가 충분히 작으므로, \(N\) 이하의 모든 정수 각각을 \(A\)와 \(B\)로 직접 나누어보는 것으로 문제를 충분히 해결할 수 있다.

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

#include <iostream>
using namespace std;

int N, A, B, ans;

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

    cin >> N >> A >> B;
    for (int i = 1; i <= N; i++) {
        int cnt = 0;
        if (i % A) cnt++;
        if (i % B) cnt++;
        if (cnt == 1) ans++;
    }
    cout << ans;
}

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

이번에 볼 문제는 백준 33170번 문제인 ブラックジャック (Blackjack)이다.
문제는 아래 링크를 확인하자.

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

주어진 세 수의 합이 21 이하인지 확인하여 대응되는 문자열을 출력하는 문제이다.

정수 세 개를 입력받고, 그 값을 합하여 출력하는 코드를 작성해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int A, B, C;

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

    cin >> A >> B >> C;
    if (A + B + C <= 21) cout << 1;
    else cout << 0;
}