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

1059번 : 좋은 구간

 

 

 

브루트포스라기보단 수학문제다. 공식을 찾아내야 풀 수 있다.

예제2에서 4 8 13 24 30이 주어진 숫자들이고 n이 10일때 [9, 10], [9, 11], [9, 12], [10, 11], [10, 12]이므로 범위안에서 시작값이 n보다 작은 수일 경우 n을 포함하는 경우와 n이 시작 값일 경우가 있다.

(확정한 범위에서 n보다 작은 수의 개수) * (확정한 범위에서 n을 포함한 큰 수의 개수) + (확정한 범위에서 n보다 큰 수의 개수)

 

import sys
l = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
n = int(sys.stdin.readline())
numbers.sort()
if n in numbers: #1
    print(0)
else:
    left_value, right_value = 0, 0
    for num in numbers:
        if num < n: #2
            left_value = num
        elif num > n and right_value == 0: #3
            right_value = num
    left_value += 1 #4
    right_value -= 1
    print((n-left_value)*(right_value-n+1)+(right_value-n)) #5

 

#1 : n이 존재하는 수이면 0을 출력

#2 : n보다 작으면 왼쪽 값에 저장

#3 : n보다 크고 처음갱신이라면 오른쪽 값에 저장

#4 : 왼쪽은 +1 오른쪽은 -1해서 범위 확정

#5 : 공식에 의한 값 출력

 

특정 원하는 구간의 범위를 산정하는 방법을 배울 수 있던 문제였다. 하지만 공식을 모르면 풀 수 없는 문제인데 분류가 수학으로 되어있는 문제들은 난이도와 상관없이 어떻게 접근해서 공식을 유추해야 할지 모르겠다.