[백준/파이썬] 1059번 좋은 구간 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1059번 좋은 구간
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

정수 집합 S가 주어질 때, 숫자 n을 포함하면서 S의 어떤 원소도 포함하지 않는 구간 [A, B]의 개수를 구하는 문제입니다.

단, A < n < B이고 A, B는 자연수입니다.

코드

l=int(input())
s=[0]+list(sorted(map(int,input().split())))
n=int(input())
i=0
while s[i]<n:i+=1
a=(n-s[i-1])*(s[i]-n)-1
print(a if a>0 else 0)

설명

n 바로 왼쪽 경계값을 L, 오른쪽 경계값을 R이라 하면 가능한 구간 수는

(n - L) * (R - n) - 1

로 계산됩니다.

코드는 정렬된 배열에서 n이 들어갈 위치를 찾아 위 공식을 적용하고, 음수가 나오는 경우 0을 출력합니다.

---

• 백준 문제풀이 전체 목록 보기

---