취미로 코딩하기

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

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

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

끌 수 있는 촛불의 개수의 형태는 일부는 몇몇 사람의 초는 $k$개를 끄고 나머지 사람의 초는 \(k+1\)개를 끄는 형태뿐임을 관찰하자. (단, 0명도 가능하다.)

따라서, N명이 꽂은 초를 각각 그 사람이 꽂은 초 중 가장 비용이 적은 것을 골라 하나씩 끄는 것을 반복하는 것으로 문제를 쉽게 해결할 수 있다.

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

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

int N, H, C, ans;
priority_queue<int, vector<int>, greater<>> pq[100], pqpq;

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

    cin >> N >> H >> C;
    for (int n = 0; n < N; n++) {
        for (int h = 0; h < H; h++) {
            int x; cin >> x;
            pq[n].push(x);
        }
    }
    for (int h = 0; h < H; h++) {
        for (int n = 0; n < N; n++) pqpq.push(pq[n].top()), pq[n].pop();
        while (!pqpq.empty() && pqpq.top() <= C) {
            C -= pqpq.top();
            pqpq.pop();
            ans++;
        }
        if (!pqpq.empty()) break;
    }

    cout << ans;
}

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

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

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

각 박스에 들어있는 크레용의 색이 겹치지 않도록 최소한의 크레용을 빼내자. 이 빼낸 크레용을 이용하여 다시 모든 박스를 서로 다른 색으로 채울 수 있음은 자명하다.

위 과정은 set 등의 자료구조를 이용하여 어렵지 않게 구현할 수 있다.

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

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

int N, K, ans;
set<string> st;

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

    cin >> N >> K;
    for (int n = 0; n < N; n++) {
        st.clear();
        for (int k = 0; k < K; k++) {
            string s; cin >> s;
            if (st.count(s)) ans++;
            else st.insert(s);
        }
    }
    cout << ans;
}

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

이번에 볼 문제는 백준 33643번 문제인 Keys, Phone, Wallet이다.
문제는 아래 링크를 확인하자.

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

주어지는 문자열 중 "keys", "phone", "wallet"이 존재하는지를 판단하자. 그리고 등장한 적이 없는 물건을 모두 출력하자. 단, 모든 문자열이 등장한 경우 "ready"를 출력하자.

이는 간단한 반복문과 조건문을 이용하여 구현할 수 있다.

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

#include <iostream>
using namespace std;

int N, cnt;
bool iskeys, isphone, iswallet;

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

    cin >> N;
    while (N--) {
        string s; cin >> s;
        if (s == "keys") iskeys = 1;
        else if (s == "phone") isphone = 1;
        else if (s == "wallet") iswallet = 1;
    }
    if (!iskeys) cout << "keys\n";
    if (!isphone) cout << "phone\n";
    if (!iswallet) cout << "wallet\n";
    if (iskeys && isphone && iswallet) cout << "ready\n";
}

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

이번에 볼 문제는 백준 2450번 문제인 모양 정돈이다.
문제는 아래 링크를 확인하자.

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

주어진 모양의 정렬 결과는 각 도형이 등장하는 순서의 경우의 수와 같은 6가지뿐임을 관찰하자.

따라서 결과로 나올 수 있는 6가지 배치 각각에 대하여 필요한 최소 맞바꾸기 횟수를 구하는 것으로 문제를 해결할 수 있다.

각 경우에 대한 최소 맞바꾸기 횟수는 permutation cycle decomposition 개념을 활용하면 어렵지 않게 구할 수 있다.

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

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

int P[3] = {0,1,2};
bool comp(int &x, int &y) {
    return P[x] < P[y];
}

int N, ans = 0x3f3f3f3f;
int A[100000], B[100000];
int cnt[3][3];

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

    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i], A[i]--;
    for (int i = 0; i < N; i++) B[i] = A[i];
    for (int k = 0; k < 6; k++) {
        sort(A, A + N, comp);
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < N; i++) {
            cnt[A[i]][B[i]]++;
        }
        int val1 = min(cnt[0][1], cnt[1][0]);
        cnt[0][1] -= val1, cnt[1][0] -= val1;
        int val2 = min(cnt[0][2], cnt[2][0]);
        cnt[0][2] -= val2, cnt[2][0] -= val2;
        int val3 = min(cnt[1][2], cnt[2][1]);
        cnt[1][2] -= val3, cnt[2][1] -= val3;
        ans = min(ans, val1 + val2 + val3 + (cnt[1][0] + cnt[0][1]) * 2);
        next_permutation(P, P + 3);
    }

    cout << ans;
}

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

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