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에서 가장 큰 정수)

 

좋은 구간 [A, B] 사이에는 집합 S의 원소가 들어있으면 안 되며, 

마지막에 주어진 n이 꼭 포함되어야 한다. 

그러므로 n과 가까운 S의 원소를 찾는다. 

예를 들어 

S = {1, 3, 5 ,10, 30} 이고

n이 7라면

[A,B]는 7의 가까운 수인 5과 10을 기준으로 정의하면된다. 

즉 [5,7] , [5,8] , [5,9] ,

[6,7] , [6,8] , [6,9] ,

[7,8] , [7,9] 

총 8 가지가 된다. 

 

#include <iostream>

using namespace std;

int main(void)
{    
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int array[50]; // L 가 50보다 작거나 같으므로 그 이상 들어오지 않는다. 
    
    int x;
    cin>>x;
    for(int i = 0; i<x; i++)
    {
        cin>>array[i];
    }
    
    int n;
    cin>>n;

    int small_n = 0;    //n보다 작은수중 제일 큰 수
    int large_n = 1001;    //n보다 큰 수중 제일 작은 수

    for(int i = 0; i<x; i++)
    {
        if(array[i]<=n && array[i] >= small_n)  
        {//n보다 작은 수 중, 제일 큰 수
            small_n = array[i];
        }
        if(array[i]>=n && array[i] <= large_n)
        {//n보다 큰 수 중, 제일 작은 수
            large_n = array[i];
        }
    }

    int result = 0;

    //small_n 과 large_n 사이의 범위를 구한다.
    //n을 포함하는
    //만약 small_n이 4, large_n이 11, n이 7이라면
    //[5,7],[5,8],[5,9],[5,10],
    // [6,7],[6,8],[6,9],[6,10],
    // [7,8],[7,9],[7,10]
    
    for(int i = small_n+1; i<n; i++)
    {   //[5,7],[5,8],[5,9],[5,10],
        // [6,7],[6,8],[6,9],[6,10]을 구한다. 
        for(int j = n; j<large_n; j++)
        {
            result++;
        }
      }

    for(int i = n+1; i<large_n; i++)
    {   //[7,8],[7,9],[7,10]을 구한다.
        result++;
    }
    
    cout<<result<<"\n";
    return 0;
}