[백준] 1059번 : 좋은 구간 (C++)

1059번 : 좋은 구간

---

문제)

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

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

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

 

 

 

입력 :

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

 

 

 

 

출력 :

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

 

 

 

 

 

풀이)

 

// 1059. 좋은 구간
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int l;
    cin >> l;
 
    vector<int> vec;
    vec.resize(l);
    for (int& ele : vec) cin >> ele;
 
    // 오름차순 정렬
    sort(vec.begin(), vec.end());
 
    int n;
    cin >> n;
 
    // 집합 S에서 n보다 큰 수 중 가장 가까운 수를 찾는다.
    int s = 0, e = 0;
    for (int i = 0; i < l; i++)
    {
        if (n < vec[i])
        {
            if( i > 0) s = vec[i - 1];
            e = vec[i];
            break;
        }
    }
 
    // 만약 n보다 작은 수 중 가장 가까운 수가 n과 같다면
    // 좋은 구간은 만들 수 없다.
    if (s == n)
    {
        cout << 0;
        return 0;
    }
 
    // n을 포함하는 좋은 구간의 수를 센다.
    int cnt = 0;
    for (int i = min(s + 1, n); i <= n; i++)
    {
        for (int j = max(i + 1, n); j <= e - 1; j++)
        {
            cnt++;
        }
    }
 
    cout << cnt;
 
    return 0;
}
 

---

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

1059번: 좋은 구간