[백준][파이썬] 1059번 : 좋은 구간(코드, 해설, 풀이)

 

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

1059번: 좋은 구간

 

 

---

- 문제

 좋은 구간의 개수를 구하는 문제이다.

---

- 해설

  좋은 구간이란 4 8 13 24 30이 주어지고 n이 10일 때 8과 13 사이에 10이 있으므로 10을 포함하는 모든 구간을 말한다. 이때 8과 13은 제외하므로 [9,10], [9,11], [9,12], [10,11], [10,12]가 된다. 이 경우 10보다 작은 9를 포함하고 있을 때 10을 포함하여 10보다 큰 경우를 모두 포함하고 있고, 10을 첫 번째 인수로 받은 경우 10보다 크고 13보다 작은 경우의 2가지만 포함하고 있는 것을 확인할 수 있다.

  위의 경우를 통해 8과 13을 제외한 9 10 11 12가 있고 n이 10이면

 

(10보다 작은 수의 개수) * (10을 포함한 10보다 큰 수의 개수) + (10보다 큰 수의 개수)

 

가 되는 것을 볼 수 있다. 이걸 공식으로 만들면 문제를 해결할 수 있다.

 

---

- 풀이

import sys
L = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
n = int(sys.stdin.readline())
nums.sort()  # 두 수 사이에 있는 n을 찾아야 하므로 정렬
if n in nums:
    print(0)
else:
    min = 0
    max = 0
    for num in nums:            # 배열중에서 n과 가장 근접한 두 수를 구한다.
        if num < n:     
            min = num
        elif num > n and max == 0:
            max = num
    max -= 1                    # 1과 7사이에 n이 2이면 1과 7은 제외
    min += 1
    print((n-min)*(max-n+1) + (max-n))
    # n보다 작은 수와 만족할 경우 + n보다 큰 수와 만족할 경우

  만약 n이 주어진 배열안에 있는 수와 일치하면 좋은 구간이 절대로 나올 수 없으므로 0을 출력하도록 한다. 그 이후에 n과 가장 근접한 두 수를 min과 max라고 명명하고 해당 숫자들은 제외해야 하니 max에 -1을 하고 min에 +1을 하도록 한다. 이후에 해설에서 구한 공식을 이용하여 정답을 구할 수 있다.