A번 문제: 부호 조정을 통한 곱의 양수화

배열에 포함된 정수들 중 -1과 1의 개수를 세어, 전체 원소의 곱이 양수가 되도록 최소 연산 횟수를 구하는 문제이다. 핵심은 음수(-1)의 개수가 홀수일 경우 하나를 제거하고 1로 변환해야 한다는 점이다. 이후 1의 개수가 -1의 개수 이상이 될 때까지 두 개씩 변환해 나간다. 이때 매번 두 개의 -1을 1로 바꾸므로 연산 횟수는 2씩 증가한다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int neg = 0, pos = 0;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            if (x == -1) neg++;
            else pos++;
        }

        int ops = 0;
        // 음수 개수가 홀수면 짝수로 만들기
        if (neg % 2 == 1 && neg > 0) {
            neg--;
            pos++;
            ops++;
        }

        // pos가 neg보다 많아질 때까지 -1을 1로 두 개씩 변환
        while (pos < neg) {
            pos += 2;
            neg -= 2;
            ops += 2;
        }

        cout << ops << '\n';
    }
    return 0;
}

B번 문제: 두 문자열로 표현된 수의 차이 최소화

두 매우 큰 수가 문자열 형태로 주어지고, 각 자리에서 숫자를 변경하여 두 수의 차이를 줄이는 문제이다. 실제로 뺄셈을 수행할 필요 없이, 첫 번째로 다른 자리에서 앞선 부분은 각 자릿수 차이의 절댓값을 더하고, 그 이후 자리는 모두 9로 만들어 최대 기여도를 반영한다. 길이가 다르면 짧은 쪽에 앞부분에 0을 추가하여 길이를 맞춘다.

#include <bits/stdc++.h>
using namespace std;

void 출력(int128 값) {
    if (값 >= 10) 출력(값 / 10);
    putchar(값 % 10 + '0');
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        string a, b;
        cin >> a >> b;

        if (a == b) {
            cout << 0 << endl;
            continue;
        }

        if (a.length() < b.length()) swap(a, b);
        // 짧은 문자열 앞에 0 삽입
        while (b.length() < a.length()) {
            b = "0" + b;
        }

        int idx = 0;
        while (idx < a.length() && a[idx] == b[idx]) idx++;

        int128 결과 = 0;
        // 일치하는 부분까지는 자릿수 차이 누적
        for (int i = 0; i <= idx; i++) {
            결과 += abs(a[i] - b[i]);
        }
        // 불일치 시작 위치 이후 모든 자리는 9로 간주
        결과 += 9 * (a.length() - idx - 1);

        출력(결과);
        cout << endl;
    }
    return 0;
}

C번 문제: 문자열 변환 게임에서의 최적 전략

Alice와 Bob이 번갈아 가며 문자열을 조작하는 게임이다. Alice는 문자열 s1을, Bob은 s2를 조작하며, 목표는 두 문자열을 일치하게 만드는 것이다. 각 플레이어는 자신의 차례에 접두사를 뒤집고 모든 비트를 반전시킬 수 있다. 해결 핵심은 두 가지 시나리오를 고려하는 것이다:

• s2를 기준으로 얼마나 많은 위치가 s1과 다른지 확인.
• s1을 뒤집었을 때 s2와 얼마나 다른지 비교.

각 경우에 대해 필요한 동작 수를 계산하고, Alice가 선공이므로 가능한 최소 값을 선택한다. 차이가 홀수냐 짝수냐에 따라 동작 수가 달라지며, 최종적으로 두 전략 중 작은 값을 출력한다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s, t_str;
        cin >> s >> t_str;

        if (s == t_str) {
            cout << 0 << endl;
            continue;
        }

        ll diff_orig = 0, diff_rev = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] != t_str[i]) diff_orig++;
        }

        reverse(s.begin(), s.end());
        for (int i = 0; i < n; i++) {
            if (s[i] != t_str[i]) diff_rev++;
        }

        ll ans = LLONG_MAX;

        // 원본 상태에서의 전략
        if (diff_orig == 1) {
            ans = min(ans, 1LL);
        } else {
            if (diff_orig % 2 == 1) {
                ans = min(ans, 2 * diff_orig - 1);
            } else {
                ans = min(ans, 2 * diff_orig);
            }
        }

        // 뒤집은 상태에서의 전략
        if (diff_rev == 0) {
            ans = min(ans, 2LL);
        } else {
            if (diff_rev % 2 == 0) {
                ans = min(ans, 2 * diff_rev - 1);
            } else {
                ans = min(ans, 2 * diff_rev);
            }
        }

        cout << ans << endl;
    }
    return 0;
}