BOJ 24023 : 아기 홍윤

• 문제 링크 : boj.kr/24023
• 난이도 : G5
• 태그 : 그리디

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for(auto &u : arr) cin >> u;

    int s, curr;
    s = curr = 0;
    for(int i = 0; i < n; i++) {
        if((k | arr[i]) > k) {
            curr = 0;
            s = i+1;
            continue;
        }
        curr |= arr[i];
        if(curr == k) {
            cout << s+1 << " " << i+1 << "\n";
            return 0;
        }
    }
    cout << -1;

    return 0;
}

---

풀이

어떤 수와 K를 OR연산한 값이 K보다 크다면, 어떤 수에는 K에 없는 1인 비트가 존재한다는 뜻이다. 따라서 이 어떤 수는 구간에 포함될 가능성이 없다. 그렇지 않은 값들로만 구간을 만들어 OR연산한 뒤, K와 같아지면 답을 출력하면 된다.