[BOJ] 13021 - 공 색칠하기

https://www.acmicpc.net/problem/13021

BOJ - 13021 - 공 색칠하기

문제 유형: 애드 혹, 수학, 조합론

문제 난이도: Silver I

시간 제한: 1초

메모리 제한: 512MB

 

문제

공 N개가 한 줄로 놓여져 있다. 공은 검정색 또는 흰색으로 칠할 수 있으며, 처음에 모든 공의 색은 흰색이다. 공은 가장 왼쪽이 1번이고, 순서대로 번호가 매겨져 있다.

오늘은 공을 칠해보려고 한다. 공은 기계를 이용해서 칠할 수 있는데, 기계는 두 정수 L과 R을 입력으로 받는다. 기계는 L번째 공부터 R번째 공까지를 흰색이나 검정색으로 모두 칠한다.

기계를 총 M번 사용했고, 이때 입력한 L과 R을 모두 알고있다. 하지만, 어떤 색으로 칠했는지는 까먹고 말았다. 

기계를 모두 M번 사용했을 때, 나올 수 있는 색 조합의 경우의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 공의 개수 N과 기계를 사용한 횟수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 50)

둘째 줄부터 M개의 줄에는 기계를 사용할 때 입력한 L과 R이 기계를 사용한 순서대로 주어진다. (1 ≤ L ≤ R ≤ N)

 

출력

첫째 줄에 나올 수 있는 색 조합의 수를 출력한다. 정답은 263-1보다 작거나 같다.

 

풀이

배열 changed[i]에는 i번째 공에 마지막으로 칠한 시도의 번호를 기록한다.

입력이 너그러워서, 무식하게 구현해도 된다.

그 뒤, 실제 changed에 남아있는 번호들의 개수를 구하고, 그를 k라 했을때,  2^k가 정답이다.

 

코드

C++

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> changed(n + 1, 0);
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        for (int j = l; j <= r; j++) {
            changed[j] = i;
        }
    }

    set<int> s;
    for (int i = 1; i <= n; i++) {
        if (changed[i] > 0) {
            s.insert(changed[i]);
        }
    }
    int k = s.size();

    cout << (1LL << k) << "\n";

    return 0;
}