취미로 코딩하기

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

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

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

현재 네 병에 담겨있는 물의 양을 4-tuple로 생각하자. 단, 없는 병의 경우 부피가 0인 병에 0인 물이 채워져있다고 생각하자.

이 때, 각 상태를 정점으로, 에서 한 번의 조작으로 변화할 수 있는 상태와의 관계를 (방향이 있는) 간선으로 생각하면 주어진 문제는 모든 병이 꽉 찬 초기상태에서 주어진 목표 상태까지의 최단거리(단, 모든 간선의 가중치는 1)를 구하는 문제로 모델링할 수 있다.

가능한 조작이 많으므로 누락되는 조작이 없게 유의하여 구현하자.

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

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

int N;
int A, B, C, D, eA, eB, eC, eD, dist[50][50][50][50];
queue<pair<pair<int, int>, pair<int, int>>> que;

void bfs() {
    dist[A][B][C][D] = 1;
    que.push({{A, B}, {C, D}});
    while (!que.empty()) {
        int a = que.front().first.first, b = que.front().first.second, c = que.front().second.first, d = que.front().second.second; que.pop();
        if (!dist[0][b][c][d]) dist[0][b][c][d] = dist[a][b][c][d] + 1, que.push({{0, b}, {c, d}});
        if (!dist[a][0][c][d]) dist[a][0][c][d] = dist[a][b][c][d] + 1, que.push({{a, 0}, {c, d}});
        if (!dist[a][b][0][d]) dist[a][b][0][d] = dist[a][b][c][d] + 1, que.push({{a, b}, {0, d}});
        if (!dist[a][b][c][0]) dist[a][b][c][0] = dist[a][b][c][d] + 1, que.push({{a, b}, {c, 0}});
        int val;
        val = min(B - b, a);
        if (!dist[a - val][b + val][c][d]) dist[a - val][b + val][c][d] = dist[a][b][c][d] + 1, que.push({{a - val, b + val}, {c, d}});
        val = min(A - a, b);
        if (!dist[a + val][b - val][c][d]) dist[a + val][b - val][c][d] = dist[a][b][c][d] + 1, que.push({{a + val, b - val}, {c, d}});
        val = min(C - c, a);
        if (!dist[a - val][b][c + val][d]) dist[a - val][b][c + val][d] = dist[a][b][c][d] + 1, que.push({{a - val, b}, {c + val, d}});
        val = min(A - a, c);
        if (!dist[a + val][b][c - val][d]) dist[a + val][b][c - val][d] = dist[a][b][c][d] + 1, que.push({{a + val, b}, {c - val, d}});
        val = min(D - d, a);
        if (!dist[a - val][b][c][d + val]) dist[a - val][b][c][d + val] = dist[a][b][c][d] + 1, que.push({{a - val, b}, {c, d + val}});
        val = min(A - a, d);
        if (!dist[a + val][b][c][d - val]) dist[a + val][b][c][d - val] = dist[a][b][c][d] + 1, que.push({{a + val, b}, {c, d - val}});
        val = min(C - c, b);
        if (!dist[a][b - val][c + val][d]) dist[a][b - val][c + val][d] = dist[a][b][c][d] + 1, que.push({{a, b - val}, {c + val, d}});
        val = min(B - b, c);
        if (!dist[a][b + val][c - val][d]) dist[a][b + val][c - val][d] = dist[a][b][c][d] + 1, que.push({{a, b + val}, {c - val, d}});
        val = min(D - d, b);
        if (!dist[a][b - val][c][d + val]) dist[a][b - val][c][d + val] = dist[a][b][c][d] + 1, que.push({{a, b - val}, {c, d + val}});
        val = min(B - b, d);
        if (!dist[a][b + val][c][d - val]) dist[a][b + val][c][d - val] = dist[a][b][c][d] + 1, que.push({{a, b + val}, {c, d - val}});
        val = min(D - d, c);
        if (!dist[a][b][c - val][d + val]) dist[a][b][c - val][d + val] = dist[a][b][c][d] + 1, que.push({{a, b}, {c - val, d + val}});
        val = min(C - c, d);
        if (!dist[a][b][c + val][d - val]) dist[a][b][c + val][d - val] = dist[a][b][c][d] + 1, que.push({{a, b}, {c + val, d - val}});
    }
}

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

    cin >> N;
    if (N == 1) cin >> A >> eA;
    else if (N == 2) cin >> A >> B >> eA >> eB;
    else if (N == 3) cin >> A >> B >> C >> eA >> eB >> eC;
    else cin >> A >> B >> C >> D >> eA >> eB >> eC >> eD;
    bfs();

    if (dist[eA][eB][eC][eD]) cout << dist[eA][eB][eC][eD] - 1;
    else cout << "NIE";
}

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

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

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

두 문자열 A와 B에 대하여 A+B에 문자열 S가 포함된 횟수는 (A에 포함된 S의 수) + (B에 포함된 S의 수) + (A와 B에 걸친 S의 수)와 같다는 점을 관찰하자.

이 점을 점화관계로 이용하면 앞 두 단계에 포함된 문자열의 수를 계속 관리해나가고 사이에 걸친 문자열의 개수를 계속 세나가는 것으로 문제를 해결할 수 있다.

한편, 문자열의 길이는 한 단계 지날 때마다 기하급수적으로 증가하므로 이를 직접 저장하면 저장해야하는 문자열의 길이가 매우 길어질 것이다. 우리는 다음 단계의 문자열을 구할 때 각각의 문자열의 앞과 뒤의, S의 길이(보다 하나 적은)만큼만의 부분문자열만 알아도 충분하므로 이 점을 이용해 저장할 문자열의 길이를 적절하게 관리해나가자.

위 관찰을 더 파고들면 더 많은 최적화 또한 가능하지만 이 문제의 해결에는 필요하지 않다. 관심이 있다면 더 생각해보자.

문제의 답이 64비트 정수 자료형의 범위를 넘을 수 있다는 점에 유의하자. 감이 잘 안 온다면, 찾아야 하는 문자열이 "a"로 주어지면 답이 피보나치 수와 같이 증가함을 관찰하고, 200번째 피보나치 수가 얼마나 큰지 확인해보자. 한편, 수가 매우 커지지는 않으므로 큰 수의 연산을 효율적으로 구현할 필요는 없다.

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

#include <iostream>
using namespace std;

int N;
string S;
string s[200], dp[200];

void calc(int idx, int val) {
    string A = dp[idx - 2], B = dp[idx - 1];
    while (A.length() < B.length()) A = "0" + A;
    while (A.length() > B.length()) B = "0" + B;
    bool carry = 0;
    int len = A.length();
    for (int i = len - 1; i > -1; i--) {
        int a = A[i] - '0', b = B[i] - '0';
        int x = a + b;
        if (carry) carry = 0, x++;
        if (x > 9) x -= 10, carry = 1;
        A[i] = '0' + x;
    }
    if (carry) A = "1" + A;
    B = to_string(val);
    while (A.length() < B.length()) A = "0" + A;
    while (A.length() > B.length()) B = "0" + B;
    carry = 0;
    len = A.length();
    for (int i = len - 1; i > -1; i--) {
        int a = A[i] - '0', b = B[i] - '0';
        int x = a + b;
        if (carry) carry = 0, x++;
        if (x > 9) x -= 10, carry = 1;
        A[i] = '0' + x;
    }
    if (carry) A = "1" + A;
    dp[idx] = A;
}

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

    cin >> S >> N;
    s[0] = "b", s[1] = "a";
    if (S == "a") dp[1] = "1";
    else dp[1] = "0";
    if (S == "b") dp[0] = "1";
    else dp[0] = "0";
    for (int i = 2; i < N; i++) {
        string tmp = "";
        if (s[i - 1].length() >= S.length() - 1) tmp += s[i - 1].substr(s[i - 1].length() - (S.length() - 1), S.length() - 1);
        else tmp += s[i - 1];
        if (s[i - 2].length() >= S.length() - 1) tmp += s[i - 2].substr(0, S.length() - 1);
        else tmp += s[i - 2];
        int tlen = tmp.length(), cnt = 0;
        for (int k = 0; k + S.length() <= tlen; k++) {
            if (tmp.substr(k, S.length()) == S) cnt++;
        }
        calc(i, cnt);
        s[i] = s[i - 1] + s[i - 2];
        if (s[i].length() >= S.length()) s[i] = s[i].substr(0, S.length()) + s[i].substr(s[i].length() - S.length(), S.length());
    }

    cout << dp[N - 1];
}

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

이번에 볼 문제는 백준 33556번 문제인 Java String Equals이다.
문제는 아래 링크를 확인하자.

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

주어지는 두 문자열 A와 B는 (1) 문자열 A가 null인 경우, (2) 문자열 A는 null이 아니지만 B는 null인 경우, (3) 문자열 A와 B 모두 null이 아닌 경우의 세 가지 경우로 나눌 수 있다.

(1)의 경우 주어지는 두 함수 모두 NullPointerException이 항상 발생함을 지문으로부터 알 수 있다. 또한 (2)의 경우 A와 B가 다름이 명백하므로 두 함수 모두 false를 반환할 것임을 알 수 있다.

그 외의 경우는 모두 입력으로 일반 문자열이 주어지는 상황이므로, 일반적인 비교와 대소문자를 무시한 비교를 구현하여 문제를 해결할 수 있다.

"null"만이 값이 존재하지 않음을 의미한다는 점에 유의하자. 즉, "Null", "NULL" 등은 "null"과 같지 않다는 점에 유의하자.

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

#include <iostream>
using namespace std;

string A, B;

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

    cin >> A >> B;
    if (A == "null") cout << "NullPointerException\nNullPointerException", exit(0);
    else if (B == "null") cout << "false\nfalse", exit(0);
    
    if (A == B) cout << "true\n";
    else cout << "false\n";

    for (auto &l:A) l = tolower(l);
    for (auto &l:B) l = tolower(l);
    if (A == B) cout << "true";
    else cout << "false";
}

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

이번에 볼 문제는 백준 33510번 문제인 이상한 나누기이다.
문제는 아래 링크를 확인하자.

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

수가 1이 될 때까지 큰 수 자료형을 이용하여 계산하는 것은 연산에 시간이 오래 걸려 실행시간이 길다.

그러나 주어진 수의 각 자리를 저장하고, 직접 위 연산을 받아올림등을 이용하여 손으로 계산하듯이 계산하면 2로 나누는 것은 뒤의 0을 제거하는 것으로, 덧셈은 변하는 자릿수만 변하므로(그리고 그 변화는 각 자리에 대하여 많아야 2번 일어나므로) 시간 내에 충분히 해결할 수 있게 된다.

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

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

int ans;
int N; bool carry, chk0;
string s;

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

    cin >> N >> s;
    for (auto &l:s) {
        if (l == '0') chk0 = 1;
    }
    if (!chk0) {
        if (s == "1") cout << 0;
        else cout << 1;
        exit(0);
    }

    for (int i = N - 1; i > 0; i--) {
        if (carry) {
            if (s[i] == '1') s[i] = '0';
            else s[i] = '1', carry = 0;
        }
        if (s[i] == '1') carry = 1, ans++;
    }
    cout << ans;
}

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

이번에 볼 문제는 백준 33541번 문제인 2025는 무엇이 특별할까?이다.
문제는 아래 링크를 확인하자.

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

주어진 수를 네 자리를 넘어가지 않을 때까지 1씩 증가시켜나가면서 조건을 만족하는 수를 찾아 문제를 해결하자.

네 자리 양의 정수는 9000개뿐이므로 이와 같은 풀이법으로도 충분히 빠르게 문제를 해결할 수 있다.

다른 방법으로, 조건을 만족하는 정수는 2025, 3025, 9801의 세 가지밖에 없다는 점을 이용하여 조건문만으로도 문제를 해결할 수도 있다.

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

#include <iostream>
using namespace std;

int N;

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

    cin >> N;
    if (N < 2025) cout << 2025;
    else if (N < 3025) cout << 3025;
    else if (N < 9801) cout << 9801;
    else cout << -1;
}

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

이번에 볼 문제는 백준 33526번 문제인 Anti-Fan Death이다.
문제는 아래 링크를 확인하자.

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

$N$이 2 이상일 때, 각 문자로 이루어진 $N\times N$블록 9개로 구성된 $3N\times 3N$ 판을 적절히 구성하면 어떤 연속한 세 개의 문자도 같은 두 개의 문자를 포함하며 각 행과 열에 각 문자가 $N$개씩 포함되게 할 수 있다는 점을 관찰하자.

따라서 $N$이 1일 때의 답을 구하고, 나머지 답을 위와 같은 방법으로 구성해 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

int N;
char A[3][3] = {{'Z','N','A'},{'N','A','Z'},{'A','Z','N'}};

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

    cin >> N;
    for (int r = 0; r < 3; r++) {
        for (int p = 0; p < N; p++) {
            for (int c = 0; c < 3; c++) {
                for (int k = 0; k < N; k++) cout << A[r][c];
            }
            cout << '\n';
        }
    }
}