[백준] 1059 - 좋은 구간 (파이썬)

1. 문제

 

 

2. 코드

l = int(input())
s = list(map(int, input().split()))
n = int(input())

s.sort()
flag = 0
small = 0
big = 0
for i in range(l):
    if s[i] == n:
        flag = 1
        break
    if s[i] < n:
        small = s[i]
    elif s[i] > n and big == 0:
        big = s[i]

if flag == 0:
    print(big-n-1 + n-small-1 + (n-small-1)*(big-n-1))

else:
    print(0)

 

 

3. 주요 알고리즘

타겟(n)보다 작은데 가장 타겟과 가까운 수(small), 타겟보다 큰데 가장 타겟과 가까운 수(big)을 찾는다.

 

그리고 big-n-1 (big과 n사이의 수의 개수)와 n-small-1 (small과 n사이의 수의 개수)를 구해서 더해준다.

그러면 예를 들어 n이 3이고 big이 5, small이 1이면, [2, 3], [3, 4]를 구한 것이다.

 

여기에 big-n-1과 n-small-1의 조합의 수를 구해준다. (n-small-1)*(big-n-1)이다. 이를 더해준다.

그러면 예를 들어 n이 3, big이 5, small이 1일 때, [2, 4]를 구해준 것이다.