이현우

컴퓨터공학과

문제 링크 : https://www.acmicpc.net/problem/33272

문제

1 이상 M 이하의 서로 다른 정수 N개를 나열하여 다음 조건을 만족하는 수열 A를 만들어 보자. A_i ⊕ A_j ≠ K (1 ≤ i < j ≤ N)

⊕ 는 Bitwise XOR 연산을 의미한다.

입력

첫째 줄에 수열 A의 길이 N과 양의 정수 M, K가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ M, K ≤ 10^9)

출력

수열 A를 만들 수 있다면 수열 A의 N개의 원소를 공백으로 구분하여 한 줄에 출력한다. 그렇지 않다면 -1을 대신 출력한다. 조건을 만족하는 출력이 여러 가지인 경우 그중 아무거나 출력한다.

예제 입력,출력

image.png

알고리즘 분류

#그리디_알고리즘 #해_구성하기

해설

특정한 조건을 만족하는 수열 A를 만들 수 있으면 해당 수열을 출력하고, 불가능하다면 -1을 출력하는 문제이다. 수열의 조건은 다음과 같다.

  1. 1 이상 M 이하의 서로 다른 N개의 정수로 구성되어야 함
  2. 수열의 임의의 두 원소 Ai, Aj에 대해 Ai ⊕ Aj ≠ K를 만족해야 함 (⊕는 XOR 연산)

가능한 정수의 범위가 10^9이고, 최대 200,000개의 서로 다른 N개 조합을 고려해야 할 수 있으므로 시간 복잡도에 유의해야 할 문제이다.

이 문제의 핵심은 그리디하게 1부터 M까지의 숫자를 순서대로 확인하며 수열에 추가할지 결정하고, 수열에 숫자를 추가할 때마다 기존에 추가된 숫자들과의 XOR 조건을 만족하는지 확인하는 방식으로 해결했다.

시간 초과가 발생할 것 같아 여러 최적화를 해두었지만, 막상 제외하고 제출해도 통과하는 것으로 보아 대단한 최적화를 요구하는 문제는 아닌 것 같다.

코드의 대략적인 로직은 다음과 같다.

  1. 예외 처리: 서로 다른 숫자 N개를 골라야 하므로, M이 N보다 작으면 애초에 불가능하다. 이 경우 -1을 출력하고 프로그램을 종료.

  2. 탐색 및 조건 검사: 1부터 M까지의 숫자 i를 순회하며 수열에 추가할지 검사.
    • 만약 수열 res에 i를 추가했을 때 조건( Ai ⊕ Aj ≠ K )이 깨지는지 확인.
    • 이 조건은 A ⊕ B ≠ K 이고, XOR의 성질에 의해 A ⊕ K ≠ B 와 동치.
    • 따라서, 새로 추가할 숫자 i에 대해 i ⊕ K가 이미 res 집합에 존재하는지 확인.
    • res.find(i ^ K) == res.end(): i ⊕ K 값이 res에 존재하지 않으면 조건을 만족하므로 i를 res에 추가.

  3. 종료 조건: 수열 res에 N개의 숫자가 채워지면 더 이상 탐색할 필요가 없으므로 반복을 즉시 종료.

  4. 결과 출력:
    • 반복이 끝난 후 res의 크기가 N이면, 조건을 만족하는 수열을 찾은 것이므로 원소들을 출력.
    • res의 크기가 N보다 작으면, 1부터 M까지 모든 숫자를 확인했지만 N개를 채우지 못한 것이므로 -1을 출력.

자료구조: 수열의 순서는 상관없고, 특정 원소의 존재 여부를 빠르게 확인해야 하므로 unordered_set (해시셋)을 사용하는 것이 효율적일 것으로 보인다.

소스코드

#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 입출력 속도 향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long M, K;
    cin >> N >> M >> K;

    // M개의 숫자 중에서 N개를 고를 수 없는 경우
    if (M < N) {
        cout << -1 << endl;
        return 0;
    }

    unordered_set<long long> res; // 해시셋 사용 (수열의 요소간 순서는 상관 없으므로)

    for (long long i = 1; i <= M && res.size() < N; i++) {
        // i ^ K 값이 res 셋에 존재하지 않으면 조건을 만족함
        if (res.find(i ^ K) == res.end()) {
            res.insert(i); // 조건을 만족하므로 숫자 추가
        }
    }

    // 조건을 만족하는 수열을 생성하지 못한 경우
    if (res.size() < N) {
        cout << -1 << endl;
    }
    else {
        // 출력 (순서는 상관 없음)
        for (long long num : res) {
            cout << num << " ";
        }
        cout << "\n";
    }

    return 0;
}

Updated:

Comments