개요

첫 CF Div.3 대회 참가 후, T2의 문제를 오독하고 T3에서 무리한 구조 설계로 실패한 경험을 바탕으로 복기하며 각 문제를 해석하고 해결 방안을 정리한다.

A. 배열 분할과 합의奇偶성

문제 요약: 주어진 배열을 두 부분으로 나누어 각 부분의 합의 홀짝성이 동일하도록 만들 수 있는지 판단한다.

해석 및 분석: 홀수(odd)와 짝수(even)의 합 연산 규칙은 다음과 같다:

• odd + odd = even
• odd + even = odd
• even + even = even

두 부분의 합의 홀짝성을 같게 하려면 전체 배열에서 홀수의 개수가 짝수여야 한다는 핵심 조건이 도출된다. 이유는 다음과 같다:

• 만약 첫 번째 그룹이 홀수 개의 홀수를 포함한다면, 두 번째 그룹도 홀수 개의 홀수를 가져야 합이 모두 홀수가 된다. 즉, 총 홀수 개수는 짝수여야 한다.
• 첫 번째 그룹이 짝수 개의 홀수를 가지면 합은 짝수가 되고, 두 번째 그룹도 짝수 개의 홀수를 가져야 한다. 이 경우 역시 총 홀수 개수는 짝수다.
• 홀수를 홀수끼리, 짝수를 짝수끼리 묶는 경우에도 전체 홀수 개수가 짝수여야 가능하다.

따라서 배열 내 홀수의 개수만 세어 짝수이면 "YES", 아니면 "NO"를 출력한다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 10010
using namespace std;
int T;
int arr[N];
int main() {
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        int odd_cnt = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &arr[i]);
            if (arr[i] % 2 != 0) odd_cnt++;
        }
        if (odd_cnt % 2 == 0) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

B. 자릿수 올림 연산으로 최댓값 만들기

문제 요약: 자연수 x의 각 자릿수에 대해 반올림(4사5입) 연산을 여러 번 적용할 수 있다. 연산 결과로 얻을 수 있는 가장 큰 값을 구한다.

해석 및 분석: 반올림 연산은 낮은 자릿수부터 수행하며, 해당 자릿수 값이 5 이상이면 1을 더하고 하위 자릿수를 모두 0으로 만든다. 최댓값을 얻기 위해 가능한 모든 반올림을 수행해야 하므로, 가장 낮은 자릿수부터 검사하며 올림이 발생하면 상위 자릿수에 1을 더하고 현재 위치를 기록한다. 마지막으로 기록된 위치 이후의 모든 자릿수를 0으로 채운다. 문자열 앞에 '0'을 추가해 최상위 자릿수 올림을 처리하고, 9+1 = 10이 되는 경우도 처리한다.

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int T;
int main() {
    scanf("%d", &T);
    while (T--) {
        string s;
        cin >> s;
        s = "0" + s;
        int last_carry = 0;
        for (int i = s.size() - 1; i > 0; --i) {
            if (s[i] == '9' + 1) {
                s[i] = '0';
                s[i - 1]++;
            }
            if (s[i] >= '5') {
                s[i - 1]++;
                last_carry = i;
            }
        }
        for (int i = 0; i < s.size(); ++i) {
            if (i == 0 && s[i] == '0')
                continue;
            if (i == last_carry) {
                for (int j = last_carry; j < s.size(); ++j)
                    printf("0");
                break;
            }
            printf("%c", s[i]);
        }
        printf("\n");
    }
    return 0;
}

C. 최소값 배열로부터 원본 배열 복원

문제 요약: 수열 A의 모든 두 원소 쌍의 최소값을 모은 배열 B가 주어진다. B는 무작위로 섞여 있을 때, 원본 배열 A의 한 가지 경우를 출력한다.

해석 및 분석: A를 오름차순 정렬하면, A[i]는 i번째 원소 이후의 모든 원소와의 쌍에서 최소값이 된다. 즉, B의 원소들을 정렬한 후, 첫 번째부터 순서대로 n-1, n-2, ..., 1개씩 그룹으로 나누어 각 그룹의 첫 원소를 A의 원소로 선택한다. 마지막 원소는 충분히 큰 값(예: 1e9)으로 설정한다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#define INF 1000000000
#define MAXN 1000005
using namespace std;
int T, b[MAXN];
int main() {
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        int cnt = n * (n - 1) / 2;
        for (int i = 0; i < cnt; ++i)
            scanf("%d", &b[i]);
        sort(b, b + cnt);
        int idx = 0;
        for (int i = 0; i < n - 1; ++i) {
            printf("%d ", b[idx]);
            idx += (n - i - 1);
        }
        printf("%d\n", INF);
    }
    return 0;
}