백준 13021 - 공 색칠하기

문제 링크: https://acmicpc.net/problem/13021 

13021번: 공 색칠하기

---

문제를 요약해봅시다.

• 입력 $L, R$에 대하여 구간 $[L, R]$에 속하는 모든 공을 흰색 또는 검은색으로 칠합니다.
• $M$번의 색칠 후 나올 수 있는 색의 조합의 개수를 구합니다.

---

어떤 공이 있을 때 이 공을 몇 번 칠하든 반드시 마지막으로 색칠한 것만이 남습니다.

즉, 마지막으로 색칠한 것이 언제 칠한 것인지를 각각의 공에 대해 구해주면 됩니다.

 

$M$번을 다 칠하고 나면 각 공이 언제 마지막으로 칠해졌는지를 알 수 있습니다. 마지막으로 칠해진 시점이 같은 공들은 반드시 같은 색을 갖게 되므로, 서로 다른 칠해진 시점의 개수를 찾아줍시다.

각 시점마다 총 2가지의 색으로 칠하는 경우가 있으므로, 시점이 $K$개일 때 답은 $2^K$가 됩니다.

 

정답이 $2^{63} - 1$이하임이 보장된다고 했으므로 비트 시프트 연산으로 간단하게 답을 구할 수 있습니다.

단 64비트 자료형을 사용해야 올바른 답을 얻을 수 있습니다.

 

시간복잡도는, 총 $M$번 최대 $N$개의 공에 대해 계산을 하는 $O(MN)$의 과정과, 공을 순회하며 서로 다른 시점의 개수를 찾는 $O(N)$의 과정이 있으므로 $O(MN) + O(N) = O(MN)$ 입니다.

---

소스코드 (C++)

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;

int main() {
    fastio;
    
    int n, k;
    cin >> n >> k;
    
    vector<int> recent_color(n + 1);
    
    for (int i = 1; i <= k; i++) {
        int l, r;
        cin >> l >> r;
        
        for (int j = l; j <= r; j++) {
            recent_color[j] = i;
        }
    }
    
    vector<bool> appeared(n + 1);
    int distincts = 0;
    
    for (int i = 1; i <= n; i++) {
        if (recent_color[i] > 0 && !appeared[recent_color[i]]) {
            appeared[recent_color[i]] = true;
            distincts++;
        }
    }
    
    cout << (1LL << distincts);
    
    return 0;
}