취미로 코딩하기

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

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

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

세 점이 모두 정수점인 정삼각형은 존재하지 않으므로, 각각의 이등변삼각형은 길이가 같은 두 변에 공통으로 포함될 꼭짓점을 먼저 정하고 그 점으로부터 거리가 같은 두 점을 고르는 식으로 모두 찾을 수 있다는 점을 관찰하자.

따라서, 각 점에 대하여 그 점을 제외한 모든 점까지의 거리를 모두 구한 뒤 그 중 같은 거리에 있는 점들끼리의 개수를 각각 이용해 문제를 해결할 수 있다.

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

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

ll N;
ll P[1000][2], A[1000];

void solve() {
    ll ans = 0;
    for (int i = 0; i < N; i++) cin >> P[i][0] >> P[i][1];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            ll dx = P[i][0] - P[j][0], dy = P[i][1] - P[j][1];
            A[j] = dx * dx + dy * dy;
        }
        sort(A, A + N);
        ll old = -1, combo = 0;
        for (int j = 0; j < N; j++) {
            if (A[j] == old) combo++;
            else old = A[j], ans += combo * (combo - 1) / 2, combo = 1;
        }
        ans += combo * (combo - 1) / 2;
    }
    cout << ans << '\n';
}

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

    cin >> N;
    while (N) solve(), cin >> N;
}

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

이번에 볼 문제는 백준 21430번 문제인 Свечки이다.
문제는 아래 링크를 확인하자.

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

어떤 직선과 그 직선 위에 놓여있지 않은 점에 대하여, 점이 직선의 어느 쪽에 있느냐에 따라 \(ax+by+c\)의 부호가 변한다는 점을 관찰하자. 또한 직선으로 나뉘어진 각 영역은 각 직선에 대하여 어느 쪽에 있는지를 모두 기록한 것으로 구분된다는 점을 관찰하자.

이를 이용하면, \(m\)개의 비트를 이용하여 각 직선마다 어느 쪽에 점이 있는지를 기록할 수 있게 된다. 이 중 중복되는 값이 있는지를 살펴 문제를 해결하자.

각 직선을 비트로 저장하는 대신 trie 자료구조를 활용해도 좋다.

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

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

int N, M, R;
int P[10000][2];
vector<bool> st[10000];

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

    cin >> N >> M >> R;
    for (int i = 0; i < N; i++) cin >> P[i][0] >> P[i][1];
    for (int i = 0; i < N; i++) st[i].resize(M);
    for (int j = 0; j < M; j++) {
        int A, B, C; cin >> A >> B >> C;
        for (int i = 0; i < N; i++) {
            if (A * P[i][0] + B * P[i][1] + C > 0) st[i][j] = 1;
        }
    }
    sort(st, st + N);
    for (int i = 0; i + 1 < N; i++) {
        if (st[i] == st[i + 1]) {
            cout << "YES";
            return 0;
        }
    }
    
    cout << "NO";
}

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

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