취미로 코딩하기

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

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

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

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