알고리즘 문제 해결: Codeforces A-E 문제 분석 및 해법

이 문서는 Codeforces 경쟁 프로그래밍 플랫폼의 특정 라운드에서 제시된 문제들(A부터 E까지)에 대한 해설과 해결 전략을 다룹니다. 각 문제의 접근 방식과 구현 코드를 상세히 설명합니다.

A. 파이값 일치 확인

주어진 문자열이 원주율(π)의 특정 자릿수와 얼마나 일치하는지 찾아야 하는 문제입니다. 여기서는 π 값의 문자열 표현이 미리 정의되어 있으며, 입력 문자열과 비교하여 불일치가 발생하는 첫 번째 지점의 인덱스를 출력합니다.

해결 전략

주어진 π 값의 문자열과 입력 문자열을 첫 번째 문자부터 순서대로 비교합니다. 문자가 일치하지 않는 순간, 해당 인덱스가 불일치가 시작된 위치가 됩니다. 만약 입력 문자열 전체가 π 값과 일치한다면, 입력 문자열의 길이가 정답이 됩니다.

코드 구현

#include <iostream>
#include <string>
#include <vector> // std::vector를 사용하지 않지만, 일반적으로 포함되는 헤더. 여기서는 <bits/stdc++.h> 대체

void 문제_A_풀이() {
    // 넉넉하게 파이(pi) 값의 문자열을 미리 정의합니다.
    // 문제에 따라 정확한 파이 상수가 아닌 특정 숫자열이 주어질 수 있습니다.
    const std::string 파이_값_문자열 = "314159265358979323846264338327"; 
    std::string 입력_숫자열;
    std::cin >> 입력_숫자열;

    int 일치하는_자릿수_개수 = 0;
    for (size_t i = 0; i < 입력_숫자열.length(); ++i) {
        if (i < 파이_값_문자열.length() && 입력_숫자열[i] == 파이_값_문자열[i]) {
            일치하는_자릿수_개수++;
        } else {
            break; // 불일치가 발생하면 중단
        }
    }
    std::cout << 일치하는_자릿수_개수 << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(false); // C++ 표준 스트림과 C 스트림 동기화 비활성화
    std::cin.tie(NULL); // cin, cout 묶음 해제 (속도 향상)

    int 테스트_케이스_수;
    std::cin >> 테스트_케이스_수;
    while (테스트_케이스_수--) {
        문제_A_풀이();
    }
    return 0;
}

B. 타이샤와 주사위

주사위 N개가 있고, 이 주사위들의 합이 R입니다. 그중 하나의 주사위 값은 M으로 이미 정해져 있으며, 나머지 N-1개 주사위의 합은 S입니다. 이제 나머지 N-1개 주사위 값을 적절히 분배하여 출력해야 합니다. 주사위 값은 최소 1 이상입니다.

해결 전략

전체 합 R에서 특정 주사위의 값 M을 제외한 나머지 N-1개 주사위의 합이 S입니다. (여기서 문제의 S는 이미 `r-m`을 의미하는 것으로 보입니다. 입력 변수 `r`이 전체 합, `s`가 다른 주사위들의 합으로 주어졌으므로, `m = r - s`입니다.) 이 S를 N-1개의 주사위에 분배해야 합니다. 가장 공평한 분배는 S를 N-1로 나눈 몫을 각 주사위에 할당하고, 나머지는 앞에서부터 하나씩 더해주는 방식입니다.

코드 구현

#include <iostream>
#include <vector>
#include <numeric> // std::accumulate (필요하다면)

void 문제_B_풀이() {
    int 주사위_총개수, 주사위_총합, 나머지_주사위_합;
    std::cin >> 주사위_총개수 >> 주사위_총합 >> 나머지_주사위_합;

    // 특정 주사위 하나의 값 (문제에서는 'm'으로 표현)
    int 특정_주사위_값 = 주사위_총합 - 나머지_주사위_합;

    // 나머지 (주사위_총개수 - 1)개의 주사위에 합 나머지_주사위_합을 분배합니다.
    int 분배할_주사위_개수 = 주사위_총개수 - 1;
    int 기본_분배_값 = 나머지_주사위_합 / 분배할_주사위_개수;
    int 추가_분배_개수 = 나머지_주사위_합 % 분배할_주사위_개수;

    // 추가 분배가 필요한 주사위들에 (기본_분배_값 + 1)을 할당
    for (int i = 0; i < 추가_분배_개수; ++i) {
        std::cout << 기본_분배_값 + 1 << ' ';
    }
    // 나머지 주사위들에 기본_분배_값을 할당
    for (int i = 0; i < 분배할_주사위_개수 - 추가_분배_개수; ++i) {
        std::cout << 기본_분배_값 << ' ';
    }
    // 마지막으로 특정 주사위 값을 출력
    std::cout << 특정_주사위_값 << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int 테스트_케이스_수;
    std::cin >> 테스트_케이스_수;
    while (테스트_케이스_수--) {
        문제_B_풀이();
    }
    return 0;
}

C. 순열 재구성

길이 N의 순열 P가 있습니다. N개의 배열이 주어지는데, 각 배열은 순열 P에서 한 요소만 제거한 형태입니다. 이 N개의 배열을 바탕으로 원래의 순열 P를 재구성해야 합니다.

해결 전략

주어진 N개의 배열 각각은 원래 순열 P에서 하나의 요소를 제거한 것입니다. 예를 들어, P = [P1, P2, ..., PN]일 때, N개의 입력 배열은 다음과 같습니다:

  • [P2, P3, ..., PN] (P1 제거)
  • [P1, P3, ..., PN] (P2 제거)
  • ...
  • [P1, P2, ..., PN-1] (PN 제거)

이 패턴을 관찰하면, 각 위치 `j` (0-indexed 또는 1-indexed)에 대해 다음을 알 수 있습니다:

  1. 위치 `j`에 원래 Pj+1 요소가 오는 경우는, Pj+1 자체가 제거되었거나 P1부터 Pj 중 하나가 제거되어 요소들이 한 칸씩 앞으로 당겨진 경우입니다.
  2. 하지만 더 간단하게, `j`번째 위치(예: 0번째)에 등장하는 모든 숫자들을 세어보면, N-1개의 배열에서는 P1이 등장하고, P1이 제거된 단 하나의 배열에서만 P2가 등장합니다. 즉, 각 위치에서 N-1번 등장하는 숫자가 바로 해당 위치의 원래 순열 요소입니다.

따라서, N-1개(0부터 N-2까지)의 각 위치 `j`에 대해, N개의 입력 배열에서 `j`번째 위치에 나타나는 숫자들의 빈도를 계산합니다. 가장 많이 등장하는 숫자(N-1번 등장하는 숫자)가 바로 순열 P의 `j`번째 요소(Pj+1)입니다. 이렇게 N-1개의 요소를 찾은 후, 1부터 N까지의 숫자 중 아직 사용되지 않은 숫자가 바로 순열 P의 마지막 요소(PN)가 됩니다.

코드 구현

#include <iostream>
#include <vector>
#include <map>
#include <numeric> // std::iota (필요하다면)

const int 최대_크기 = 105; // N의 최대값

void 문제_C_풀이() {
    int 순열_크기;
    std::cin >> 순열_크기;

    // 입력된 N개의 부분 순열을 저장할 2D 벡터
    std::vector<std::vector<int>> 부분_순열들(순열_크기, std::vector<int>(순열_크기 - 1));

    // 각 위치(열)마다 숫자의 빈도를 세기 위한 맵 배열
    // map[위치_인덱스][숫자_값] -> 빈도수
    std::vector<std::map<int, int>> 위치별_숫자_빈도(순열_크기 - 1);

    for (int i = 0; i < 순열_크기; ++i) {
        for (int j = 0; j < 순열_크기 - 1; ++j) {
            std::cin >> 부분_순열들[i][j];
            위치별_숫자_빈도[j][부분_순열들[i][j]]++;
        }
    }

    std::vector<int> 재구성된_순열(순열_크기);
    std::vector<bool> 사용된_숫자(순열_크기 + 1, false); // 1부터 순열_크기까지의 숫자를 추적

    // 순열의 N-1개 요소를 찾습니다.
    for (int j = 0; j < 순열_크기 - 1; ++j) {
        int 가장_많이_등장한_숫자 = -1;
        int 최대_빈도 = 0;
        
        for (auto const& [숫자, 빈도] : 위치별_숫자_빈도[j]) {
            if (빈도 > 최대_빈도) {
                최대_빈도 = 빈도;
                가장_많이_등장한_숫자 = 숫자;
            }
        }
        재구성된_순열[j] = 가장_많이_등장한_숫자;
        사용된_숫자[가장_많이_등장한_숫자] = true;
    }

    // 마지막으로 사용되지 않은 숫자(N번째 요소)를 찾습니다.
    int 마지막_요소 = -1;
    for (int i = 1; i <= 순열_크기; ++i) {
        if (!사용된_숫자[i]) {
            마지막_요소 = i;
            break;
        }
    }
    재구성된_순열[순열_크기 - 1] = 마지막_요소;

    for (int i = 0; i < 순열_크기; ++i) {
        std::cout << 재구성된_순열[i] << (i == 순열_크기 - 1 ? "" : " ");
    }
    std::cout << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int 테스트_케이스_수;
    std::cin >> 테스트_케이스_수;
    while (테스트_케이스_수--) {
        문제_C_풀이();
    }
    return 0;
}

D. 마트료시카 인형

여러 크기의 마트료시카 인형들이 주어졌을 때, 이 인형들을 최대한 적은 수의 독립적인 마트료시카 세트로 구성해야 합니다. 마트료시카 세트는 크기가 연속적인 인형들(예: 1, 2, 3)로 구성됩니다. 즉, 크기 K의 인형은 크기 K-1의 인형 안에 들어갈 수 있습니다.

해결 전략

이 문제는 그리디(Greedy) 알고리즘으로 해결할 수 있습니다. 먼저 모든 인형의 크기를 오름차순으로 정렬합니다. 그리고 각 인형을 순서대로 처리하면서 가능한 경우 기존 세트에 연결하고, 그렇지 않으면 새로운 세트를 시작합니다.

std::map<int, int>을 사용하여 현재 열려 있는 마트료시카 세트의 '가장 바깥 인형 크기'를 추적합니다. 맵의 키는 현재 세트의 가장 바깥 인형의 크기이고, 값은 해당 크기의 인형이 몇 개나 '열려 있는지'를 나타냅니다. 예를 들어, 크기 5의 인형이 가장 바깥에 있는 세트가 2개라면 map[5] = 2가 됩니다.

인형을 순회하면서, 현재 인형의 크기가 current_doll_size라고 할 때:

  1. open_dolls[current_doll_size - 1] (즉, current_doll_size - 1 크기의 인형이 가장 바깥에 있는 세트)가 존재한다면, 이 인형을 기존 세트에 연결할 수 있습니다. 이 세트를 하나 사용했으므로 open_dolls[current_doll_size - 1] 값을 1 감소시키고, 이제 current_doll_size 인형이 가장 바깥에 있는 세트가 되었으므로 open_dolls[current_doll_size] 값을 1 증가시킵니다.
  2. 만약 current_doll_size - 1 크기의 인형을 가진 세트가 없다면, current_doll_size 인형은 새로운 세트의 시작이 되어야 합니다. 이 경우 전체 세트의 개수를 1 증가시키고, open_dolls[current_doll_size] 값을 1 증가시킵니다.

이렇게 하면 항상 가장 작은 크기의 인형부터 적절히 세트를 구성하여 최소 개수의 세트를 유지할 수 있습니다.

코드 구현

#include <iostream>
#include <vector>
#include <algorithm> // std::sort
#include <map>

const int 최대_인형_개수 = 2e5 + 5;

void 문제_D_풀이() {
    int 인형_총개수;
    std::cin >> 인형_총개수;

    std::vector<int> 인형_크기들(인형_총개수);
    for (int i = 0; i < 인형_총개수; ++i) {
        std::cin >> 인형_크기들[i];
    }

    // 인형 크기를 오름차순으로 정렬
    std::sort(인형_크기들.begin(), 인형_크기들.end());

    // 현재 열려 있는 마트료시카 세트의 가장 바깥 인형 크기별 개수
    // 키: 가장 바깥 인형 크기, 값: 해당 크기의 인형이 바깥에 있는 세트의 개수
    std::map<int, int> 열린_인형_세트;

    int 총_세트_개수 = 0;
    for (int 크기 : 인형_크기들) {
        // 현재 인형보다 1 작은 크기의 인형이 바깥에 있는 세트가 있는지 확인
        if (열린_인형_세트[크기 - 1] > 0) {
            // 있다면 기존 세트에 현재 인형을 연결
            열린_인형_세트[크기 - 1]--;
        } else {
            // 없다면 새로운 세트 시작
            총_세트_개수++;
        }
        // 현재 인형이 가장 바깥에 있는 세트의 개수를 증가
        열린_인형_세트[크기]++;
    }

    std::cout << 총_세트_개수 << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int 테스트_케이스_수;
    std::cin >> 테스트_케이스_수;
    while (테스트_케이스_수--) {
        문제_D_풀이();
    }
    return 0;
}

E. 블라드와 두 숫자

주어진 양의 정수 X에 대해, 두 개의 음이 아닌 정수 A와 B를 찾아야 합니다. 이때, A + B = X 이고 A XOR B = X 조건을 모두 만족해야 합니다.

해결 전략

비트 연산의 중요한 속성을 활용합니다: 임의의 두 음이 아닌 정수 A와 B에 대해, A + B = (A XOR B) + 2 * (A AND B) 입니다. 문제에서 A + B = X 이고 A XOR B = X 라고 주어졌으므로, 이 관계식에 대입해봅시다.

X = X + 2 * (A AND B)

이 식을 정리하면 2 * (A AND B) = 0이 됩니다. 즉, A AND B = 0입니다.

결론적으로, 우리는 A + B = X 이고 A AND B = 0 인 두 정수 A와 B를 찾아야 합니다. A AND B = 0 이라는 조건은 A와 B의 이진 표현에서 동시에 1인 비트가 없다는 것을 의미합니다. 또한, A AND B = 0 인 경우 A + B = A OR B가 성립합니다. 따라서 A OR B = X 입니다.

즉, 이 문제는 A AND B = 0 이고 A OR B = X 이면서 A + B = X 인 A, B를 찾는 문제입니다. A + B = A OR B가 성립하려면 A AND B = 0 이어야 합니다. 따라서 이 문제는 A AND B = 0 이고 A OR B = X 를 만족하는 A, B를 찾는 것으로 귀결됩니다. 이러한 A, B는 항상 존재합니다. 예를 들어 A = X, B = 0은 항상 두 조건을 만족합니다.

하지만 경쟁 프로그래밍 문제에서 이렇게 단순한 답을 요구하는 경우는 드뭅니다. 종종 문제 설명의 미묘한 차이(예: "양의 정수" A, B를 찾아야 하는 경우 등)가 있거나, 또는 문제 출제자가 "A + B = 2*X, A XOR B = X"와 같은 다른 흔한 변형 문제를 의도했을 수 있습니다. 원본 게시글의 저자 역시 이 변형 문제를 해결하는 방식으로 코드를 작성했습니다. 이 변형 문제의 해결책은 다음과 같습니다:

A + B = 2 * X 이고 A XOR B = X 인 A, B를 찾을 때:

  1. 2 * X = X + 2 * (A AND B) 에서 X = 2 * (A AND B) 가 됩니다. 이는 X가 반드시 짝수여야 함을 의미합니다. 만약 X가 홀수라면 해가 없으므로 -1을 출력합니다.
  2. X가 짝수일 경우, A AND B = X / 2 가 됩니다.
  3. 이제 A XOR B = X 이고 A AND B = X / 2 인 A, B를 찾아야 합니다. 알려진 해결책 중 하나는 A = (X / 2) + X 그리고 B = X / 2 입니다. 이 값을 확인해봅시다.
    • A + B = (X/2 + X) + X/2 = X/2 + X + X/2 = 2X. (주어진 합 조건 만족)
    • A XOR B = (X/2 + X) XOR (X/2). 이 식은 (3X/2) XOR (X/2) 로, X의 비트 패턴에 따라 달라집니다. 특히, (X/2) AND (X) = 0 (즉, X의 이진 표현에서 어떤 비트가 1이면, 그 바로 왼쪽 비트는 0이어야 함) 조건이 만족되면 (3X/2) XOR (X/2) = X가 성립합니다. 이 조건은 X/2 & (X/2 << 1) == 0과 같습니다.

따라서, X가 홀수이거나 (X/2 XOR 3X/2) != X인 경우 -1을 출력하고, 그렇지 않으면 X/2와 3X/2를 출력합니다.

코드 구현

#include <iostream>

void 문제_E_풀이() {
    long long 목표_XOR_값; // 문제에서 x로 주어지는 값
    std::cin >> 목표_XOR_값;

    // 만약 목표_XOR_값(X)이 홀수라면, X = 2 * (A AND B) 조건이 만족될 수 없으므로 해가 없습니다.
    if (목표_XOR_값 & 1) {
        std::cout << -1 << std::endl;
        return;
    }

    // A = X/2, B = 3X/2 가 유력한 후보 해입니다.
    // 이 A, B는 (A + B) = 2*X를 만족합니다.
    long long 후보_A = 목표_XOR_값 / 2;
    long long 후보_B = 후보_A * 3; // 또는 목표_XOR_값 + 후보_A;

    // A + B = 2 * 목표_XOR_값 인지 확인합니다.
    // (후보_A + 후보_B) / 2 == 목표_XOR_값 이라는 조건은
    // (X/2 + 3X/2) / 2 == X  -> (2X) / 2 == X -> X == X 이므로 항상 참입니다.
    // 따라서 이 부분의 조건은 생략하고 XOR 조건만 확인합니다.

    // A XOR B = 목표_XOR_값 인지 확인합니다.
    if ((후보_A ^ 후보_B) != 목표_XOR_값) {
        std::cout << -1 << std::endl;
    } else {
        std::cout << 후보_A << ' ' << 후보_B << std::endl;
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int 테스트_케이스_수;
    std::cin >> 테스트_케이스_수;
    while (테스트_케이스_수--) {
        문제_E_풀이();
    }
    return 0;
}

태그: C++ 알고리즘 경쟁프로그래밍 그리디알고리즘 비트연산

8월 28일 08:30에 게시됨

인기 태그

©2026 괴물 클럽