[C/C++] 백준 - 1059번 : 좋은 구간

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

1059번: 좋은 구간

문제

정수 집합 S가 주어졌을때, 다음 조건을 만족하는 구간 [A, B]를 좋은 구간이라고 한다.

• A와 B는 양의 정수이고, A < B를 만족한다.
• A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다.

집합 S와 n이 주어졌을 때, n을 포함하는 좋은 구간의 개수를 구해보자.

입력

첫째 줄에 집합 S의 크기 L이 주어진다. 둘째 줄에는 집합에 포함된 정수가 주어진다. 셋째 줄에는 n이 주어진다.

출력

첫째 줄에 n을 포함하는 좋은 구간의 개수를 출력한다.

제한

• 1 ≤ L ≤ 50
• 집합 S에는 중복되는 정수가 없다.
• 집합 S에 포함된 모든 정수는 1보다 크거나 같고, 1,000보다 작거나 같다.
• 1 ≤ n ≤ (집합 S에서 가장 큰 정수)

---

간단한 수학 문제이다. 문제 조건을 보면 L의 조건이 매우 작다. 50밖에 되지 않기 때문에 사실 모든 구간을 모두 확인하고 문제 조건에 맞는지 확인해도 많은 시간이 걸리지 않는다.

 

하지만 조금 더 효율적으로 해결하기 위해서는 문제에 주어진 조건을 활용해야한다.

A <= x <= B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다.

 

 

Step 1.

위 조건을 통해 우리는 x가 들어갈 수 있는 가장 큰 구간을 먼저 정해준다.

 

Step 2.

위에서 알아낸 가장 큰 구간에서 생성할 수 있는 작은 구간들을 모두 만들어보는 완전탐색 알고리즘을 작성한다.

 

Step 3.

Step 2에서 만든 구간 안에 N이 포함되어 있는지 확인하는 알고리즘을 작성한다. N이 들어가 있는 구간의 개수를 세어주면 된다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 987654321
#define endl '\n'

using namespace std;

int L, N;
long long answer;
vector<int> ps;
bool isin[1000 + 1];

void input(){
    cin >> L;
    ps.resize(L);
    for(int i=0;i<L;i++){
        cin >> ps[i];
        isin[ps[i]] = true;
    }
    cin >> N;
}

void dfs(vector<int> &temp, vector<int> &as, int start){
    if(as.size() == 2){
        if(as[0] <= N && N <= as[1]) {
            answer++;
        }
        return;
    }

    for(int i=start; i<temp.size();i++){
        as.push_back(temp[i]);
        
        dfs(temp, as, i+1);

        as.pop_back();
    }
}

pair<int, int> findOffsetLimit(){
    pair<int, int> info;
    for(auto &t : ps){
        if(t == N) return {0, 0};
        if(t > N){
            info.second = t;
            break;
        }
        else{
            info.first = t;
        }
    }
    return info;
}

vector<int> init_vector(int offset, int limit){
    vector<int> temp;
    for(int start = offset + 1; start < limit; start++){
        temp.push_back(start);
    }
    return temp;
}

long long solution(){
    if(isin[N]) return 0;
    sort(ps.begin(), ps.end());

    pair<int, int> info = findOffsetLimit();
    if(!info.first && !info.second) return 0;

    vector<int> temp = init_vector(info.first, info.second);

    vector<int> as;
    for(int i=0;i<temp.size();i++){
        as.push_back(temp[i]);

        dfs(temp, as, i+1);

        as.pop_back();
    }
    
    return answer;
}

int main(){
    fastio;
    input();
    cout << solution() << endl;

    return 0;
}