[Python] 백준 1059번 - 좋은 구간

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

1059번: 좋은 구간

 

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 수학
 - 브루트포스 알고리즘
 - 정렬

문제

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

---

처음엔 문제 이해가 안되어서 여러 번 생각해 보았다.

 

예제 1을 예시로 들면

 

2를 반드시 포함하며 S[i]와 S[i+1] 사이의 값으로 조합을 만드는 것이다.

 

그래서 [2, 3], [2, 4], [2,5], [2, 6]  되는 것이다.

 

이 문제에서 중요한 점은

 

n은 1부터 시작하며 S의 가장 큰 정수까지 확인하는 것이다.

 

그러므로 S[0]이 어디서부터 시작하며 n의 값이 어떤지 확인이 중요했다.

 

import sys
input = sys.stdin.readline

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

def check(a, n, b):
    if a == n:
        return b-n
    elif b == n:
        return n-a
    else:
        return (b-n+1)*(n-a) + (b-n)

cnt = 0
if S[0] > n:
    cnt = check(1, n, S[0]-1)
else:
    for i in range(L):
        if S[i] < n < S[i+1]:
            cnt = check(S[i]+1, n, S[i+1]-1)
print(cnt)

 

여기서 중요한 점은

 

(b-n+1) * (n-a) + (b-n)

이게 어떻게 나온거냐인데

 

이는 n이 S[i]+1 < n < S[i+1] -1 을 충족할 때 그 사이 개수를 찾는 식이다.

 

내가 직접 생각했따!

 

아주 후련하다.