백준 좋은구간 1059

좋은 구간 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

17405

4824

4121

28.634%

문제

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

####

양의 정수 조건때문에 다른 분이 작성하신 부분 참고

num.append(0)

위와 같이 하지 않으면 

n이 집합 s 중 가장 작은 값보다 더 작을 때 답이 구해지지 않음,

양의 정수 조건이 있으므로 0보단 크게

 

 

정렬된 배열 

1 4 7 10 19 가 있을 때

n이 14라면

좋은 구간은

11 ~ 18 의 수 중 두 숫자를 고른 쌍을

구간으로 하는 것 중에

14를 범위안에 가지고 있는 구간을 뜻한다

 

11 ~ 18 범위 내에서 좋은 구간이 가능한 경우는 3가지다.

12, 14 처럼 'n보다 작은수' 와 'n' 을 구간으로 하는 경우

14, 17 처럼 'n'과 'n보다 큰수'를 구간으로 하는 경우

12, 17 처럼 'n'이 구간 안에 있는 경우

 

위 3가지 식을 한번에 식으로 나타내면 

(n-a)* (b-n) -1 이다.

 

 

만약 n이 집합s에 이미 있는 경우-

애초에 조건에 의해 n을 포함하는 좋은 구간이 생길 수 없으므로 0이다.

l = int(input())

num = list(map(int, input().split()))

n = int(input())

a,b = 0,0

num.append(0)

num = sorted(num)

#print(num)

for i in range(len(num)-1):

    if num[i] < n and num[i+1] > n:

        a= num[i]

        b= num[i+1]

        print((n-a)*(b-n)-1)

        break

    elif num[i] == n or num[i+1]==n:

        print(0)

        break