[Baekjoon/C++] 32290번 - MEX vs OR

[백준] Baekjoon Online Judge

문제로 이동

 

문제

음이 아닌 정수로 구성된 수열 $a$가 주어질 때, 함수 mex(a)는 a에 포함되지 않은 가장 작은 음이 아닌 정수를 의미합니다.

 $\text{mex}$에 수열을 대입한 예시에는 다음이 있습니다.

•  mex([1,2,3,4,5]) = 0
•  mex([0,1,2,3,4]) = 5
•  mex([0,1,2,4,5]) = 3

음이 아닌 두 정수 x와 y가 주어질 때, x|y를 x와 y의 비트 OR이라고 부르며, 다음의 규칙에 따라 정의합니다.

• 2진법에서 x와 y 중 적어도 하나의 i번째 자리가 1이라면 x|y의 i번째 자리가 1입니다.
• 2진법에서 x와 y 둘 모두 i번째 자리가 0이라면 x|y의 i번째 자리가 0입니다.

두 정수의 비트 OR을 구한 예시에는 다음이 있습니다.

•  2|4=010_2 | 100_2=110_2=6
• 3|6=011_2 | 110_2=111_2=7
•  5|4=101_2 | 100_2=101_2=5

 l <= r을 만족하는 음이 아닌 세 정수 l, r, x가 주어집니다. 여러분은 다음 수식의 값을 구해야 합니다.

mex([(l|x), ((l+1)|x), ..., ((r-1)|x), (r|x)])

 

입력

한 줄에 세 정수 l, r, x가 공백으로 구분되어 주어집니다. (0 <= l <= r <= 1,000, 0 <= x <= 1,000)

 

출력

한 줄에 문제의 정답을 출력합니다.

 

---

풀이

#include <iostream>
using namespace std;

bool arr[1000000];

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

    int l, r, x;
    cin >> l >> r >> x;

    for (int i = l; i <= r; i++) arr[i | x] = true;

    for (int i = 0; ; i++) {
        if (!arr[i]) {
            cout << i << '\n';
            break;
        }
    }

    return 0;
}

 l | x부터 r | x까지의 답을 arr에 표시하고, for문을 통해 가장 왼쪽에 있는 표시되지 않는 칸을 찾아 출력한다.