취미로 코딩하기

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

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

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

이번에 볼 문제는 백준 33169번 문제인 所持金 (Money On Me)이다.
문제는 아래 링크를 확인하자.

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

1000엔 지폐 \(A\)장은 \(1000A\)엔의 가치와 같고 10000엔 지폐 \(B\)장은 \(10000B\)엔의 가치와 같다. 따라서 비타로가 가진 총 액수는 위의 두 값의 합인 \(1000A+10000B\)와 같다.

위의 값을 출력하여 문제를 해결하자.

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

#include <iostream>
using namespace std;

int A, B;

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

    cin >> A >> B;
    cout << A * 1000 + B * 10000;
}

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

이번에 볼 문제는 백준 33168번 문제인 三角足し算 (Triangle Addition)이다.
문제는 아래 링크를 확인하자.

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

주어진 계산 방법을 따라서 이차원 배열의 삼각형 모양 영역을 채우는 것으로 문제를 해결할 수 있다. 이는 이차원 배열과 반복문을 이용해 구현해낼 수 있다.

또는 한 행의 계산이 끝나고 그 행의 값을 출력하면 그 행의 값을 마지막까지 보관하고 있을 필요가 없다는 점을 이용하여 아래의 코드와 같이 일차원 배열만으로도 해결할 수도 있다.

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

#include <iostream>
using namespace std;

int N;
int A[10];

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

    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int k = N - 1; k > 0; k--) {
        for (int i = 0; i < k; i++) {
            cout << (A[i] += A[i + 1]) << ' ';
        }
        cout << '\n';
    }
}