취미로 코딩하기

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

이번에 볼 문제는 백준 27222번 문제인 Штангист이다.
문제는 아래 링크를 확인하자.

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

각각의 날에 대하여 그 날 훈련을 했는지, 했다면 체중이 증가했는지를 확인해 그 증가량을 모두 합하는 것으로 답을 구할 수 있다.

조건문과 반복문을 활용하여 위 내용을 구현해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N, ans;
bool A[1000];

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

    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) {
        int L, R; cin >> L >> R;
        if (A[i]) ans += max(R - L, 0);
    }
    cout << ans;
}

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

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

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

문자열 "ABC"에 주어진 규칙대로 변화를 1회 이상 주어 얻은 어떤 문자열을 S라 하자. 이 때, S의 이전 단계는 무엇인지 역추적할 수 있을까?

S의 부분문자열로 "ABC"가 존재하지 않는다면 어떤 변화로도 해당 문자열을 얻을 수 없을 것이다. 따라서 S는 부분문자열로 "ABC"를 적어도 하나 포함해야 한다. 한편, 모든 부분문자열 "ABC"는 이전 단계에서 바뀐 결과물이라는 점도 관찰할 수 있다. 이전 단계에서 어떤 문자를 ABC로 바꿔서 기존 문자와 연결된 새로운 "ABC"를 얻을 수는 없으며, 이전 단계에 있던 것이 그대로 오는 것도 불가능(어떤 연산을 해도 A나 B나 C가 있으므로 변화가 생김)하기 때문이다.

또한 이 "ABC"들이 어떤 문자였는지는 해당 문자열의 남은 다른 문자들 중 없는 문자가 되어야 한다는 점도 관찰하자. 이 때 남은 다른 문자가 0, 1, 3종류이면 불가능함을 확인하자.

위 관찰을 활용하여 주어진 문자열을 역추적해 문제를 해결하자.

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

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

string s, ss;

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

    cin >> s;

    while (s != "ABC") {
        bool chk = 0;
        ss.clear();
        for (auto &l:s) {
            ss += l;
            if (ss.length() > 2 && ss.substr(ss.length() - 3, 3) == "ABC") {
                ss.pop_back();
                ss.pop_back();
                ss.pop_back();
                ss += 'D';
                chk = 1;
            }
        }
        if (!chk) break;
        bool chkA = 0, chkB = 0, chkC = 0;
        for (auto &l:ss) {
            if (l == 'A') chkA = 1;
            else if (l == 'B') chkB = 1;
            else if (l == 'C') chkC = 1;
        }
        if (chkA && chkB && chkC) break;
        if (chkA && chkB) {
            for (auto &l:ss) {
                if (l == 'D') l = 'C';
            }
        }
        else if (chkB && chkC) {
            for (auto &l:ss) {
                if (l == 'D') l = 'A';
            }
        }
        else if (chkC && chkA) {
            for (auto &l:ss) {
                if (l == 'D') l = 'B';
            }
        }
        else break;
        swap(s, ss);
    }

    if (s == "ABC") cout << "Yes";
    else cout << "No";
}

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

이번에 볼 문제는 백준 10714번 문제인 케이크 자르기 2이다.
문제는 아래 링크를 확인하자.

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

주어진 원형 수열을 각각의 위치에서 끊으면 선형 수열이 됨을 관찰하자. 또한, 이러한 선형수열에서 양 끝의 원소에 대해 문제에서 주어진 규칙과 같이 케이크를 가져가는 것은 원형 수열에서 첫 조각을 빼고 난 뒤의 일과 대응시킬 수 있다.

따라서 문제의 답은 주어진 원형 수열을 각각의 위치에서 끊은 각각의 경우를 조사해 구할 수 있다.

한편, 선형 배열에서의 주어진 문제는 구간DP로 어렵지 않게 풀 수 있으므로 문제가 해결된다.

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

#include <iostream>
using namespace std;
typedef long long ll;

ll N, ans;
ll A[2000];
ll dp[2000][2000];
bool visited[2000][2000];

ll func2(int L, int R);

ll func1(int L, int R) {
    if (L == N) L = 0;
    if (R < 0) R = N - 1; 
    if (visited[L][R]) return dp[L][R];
    visited[L][R] = 1;
    if (L == R) return dp[L][R] = A[L];
    else return dp[L][R] = max(A[L] + func2(L + 1, R), A[R] + func2(L, R - 1));
}

ll func2(int L, int R) {
    if (L == N) L = 0;
    if (R < 0) R = N - 1; 
    if (visited[L][R]) return dp[L][R];
    visited[L][R] = 1;
    if (L == R) return 0;
    if (A[L] > A[R]) return dp[L][R] = func1(L + 1, R);
    else return dp[L][R] = func1(L, R - 1);
}

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

    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    ans = func1(0, N - 1);
    for (int i = 1; i < N; i++) ans = max(ans, func1(i, i - 1));

    cout << ans;
}

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

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

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

어떤 음이 아닌 정수 \(a\)에 대하여 이 수와 xor연산을 해 \(K\)가 되는 수는 두 수의 xor뿐임을 관찰하자.

\(K\)는 0이 아니므로, 위 관찰을 이용하면 어떤 한 정수를 수열에 넣고 해당 수와 \(k\)의 xor을 이후에 넣지 않는 것을 반복하는 방식으로 수열을 구성해 문제를 해결할 수 있다.

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

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

int N, M, K;
bool visited[400001];
vector<int> ans;

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

    cin >> N >> M >> K; ans.reserve(N);
    for (int i = 1; i <= M && ans.size() < N; i++) {
        if (visited[i]) continue;
        if ((i ^ K) < 400001) visited[i ^ K] = 1;
        ans.emplace_back(i);
    }
    if (ans.size() < N) cout << -1;
    else {
        for (auto &x:ans) cout << x << ' ';
    }
}

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

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