1059 좋은 구간

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

1059번: 좋은 구간

---

접근

설명이 다소 난해하다... N을 포함하는 범위를 만들되, 그 범위 안에 집합의 원소가 속하면 안된다. 

 

만약 N이 집합의 원소로 존재하면 어떻게 해서든지 문제의 조건을 만족할 수 없어서 0을 출력한다.

 

예를 들어 N을 5라고 하고 집합 S의 원소들을 {3, 1, 10, 8}이라고 할 때 집합의 원소들을 포함하지 않으면서 N을 포함하는 범위를 만들면 [4, 5], [4, 6], [4, 7], [5, 6], [5, 7]이 된다.

 

그러려면 N보다 작은 집합의 원소들 중 제일 큰 값(A)과 N보다 큰 집합의 원소들 중 제일 작은 값(B)을 구한 다음 A와 B사이에 있는 정수들을 구간으로 설정하면 된다.

 

이렇게 하면 다른 원소들은 포함하지 않고 순수하게 N만 포함하는 구간이 나타난다.

 

범위의 개수를 구하려면 N보다 같거나 작은 수의 개수 * N보다 같거나 큰 수의 개수를 구하면 된다.

 

A가 3, B가 9일 때 이 범위 안에서 N보다 같거나 작은 수가 3개고 N보다 같거나 큰 수가 3개다. 

 

따라서 주황색 동그라미 개수 * 파란색 동그라미 개수가 이 문제의 답인데, [6, 6]같은 경우는 없어야 한다. 문제에서 구간을 나타내는 값은 서로 같지 않다고 하기 때문이다.

 

그래서 [N, N]으로 이루어진 범위는 빼기 위해 구한 값에서 1을 뺀다.

---

#include <iostream>
int main() {
  int A, B, L, S[50], N;
  scanf("%d", &L);
  for (int i = 0; i < L; i++) {
    scanf("%d", &S[i]);
  }
  scanf("%d", &N);
  int below = 0, above = 1000;
  for (int i = 0; i < L; i++) {
    if (S[i] > N) {
      above = above > S[i] ? S[i] : above;
    } else if (S[i] < N) {
      below = below < S[i] ? S[i] : below;
    } else {
      printf("0");
      return 0;
    }
  }
  printf("%d", (N - below) * (above - N) - 1);
}