BOJ: 1059

Posted on In

문제

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

Solution

입력 구현

1
2
3
4
5
6
7
import sys

read = sys.stdin.readline

L = int(read())
S = list(map(int, read().split()))
n = int(read())

예외 처리

1
2
3
if n in S:
  print(0)
  exit()

조건 정의 후 조합을 통한 Brute Force 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from itertools import combinations

S.append(n)
S.sort()
tmp = S.index(n)

res = 0
if tmp == 0:
  for i in combinations(range(1, S[tmp + 1]), 2):
    if i[0] <= n <= i[1]:
      res += 1
else:
  for i in combinations(range(S[tmp - 1] + 1, S[tmp + 1]), 2):
    if i[0] <= n <= i[1]:
      res += 1
  
print(res)
  • 예외 처리를 통해 S 내에 n이 포함되지 않기 때문에 n을 추가하고 정렬한 뒤 인덱스 tmp 정의
  • tmp가 0인 경우 (n이 S 내에서 가장 작은 경우)
    • 1 이상 S[tmp + 1] - 1 (S 내에서 n 다음으로 큰 수) 이하의 범위에서 2개의 숫자를 조합하고 해당 구간이 n을 포함한 경우 결과값 res 1 증가
  • tmp가 그 외의 상황인 경우
    • S[tmp - 1] + 1 이상 S[tmp + 1] - 1 이하의 범위에서 위와 동일한 방법 사용