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

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

1059번: 좋은 구간

Problem

• 집합 S와 n이 주어졌을 때, n을 포함하는 좋은 구간의 개수를 구해보자.

조건

정수 집합 S가 주어졌을때, 다음 조건을 만족하는 구간 [A, B]를 좋은 구간이라고 한다.

• A와 B는 양의 정수이고, A < B를 만족한다.
• A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다.
• 1 ≤ L ≤ 50
• 집합 S에는 중복되는 정수가 없다.
• 집합 S에 포함된 모든 정수는 1보다 크거나 같고, 1,000보다 작거나 같다.
• 1 ≤ n ≤ (집합 S에서 가장 큰 정수)

SOL

우선, 좋은구간이 이해가 잘 안가서, input 과 output을 보면서 , 이해를 천천히 해보았다.

4
1 7 14 10
2

 

 

문제에 주어진 2가지 조건으로 인해서, 집합 S는 정렬이 되어 있어야하는걸 알 수 있다.

왜냐하면, A<B 이고, A<=x<=B를 만족하는 정수 x가 집합 S에 속하지 않고, 집합 S에는 중복되는 숫자가 없기 때문에, A,B사이에 숫자가 집합 S에 없으려면 우선 S를 정렬 시켜서 A,B를 순차적으로 생각 해줘야한다.

 

example input의 좋은 구간

if n=2

[2,3],[2,4],[2,5],[2,6] 

if n=3

[2,3],[2,4],[2,5],[2,6]

[3,4],[3,5],[3,6]

if n=4

[2,4],[2,5],[2,6]

[3,4],[3,5],[3,6]

[4,5],[4,6]

 

규칙을 생각해보면, n을 기준으로, "n보다 작은 수 중에서, 제일 큰 수(min_val) ~ n보다 큰 수 중에서, 제일 작은 수(max_val)"까지 좋은 구간을 다 구해주게 된다.

부등호로 나타낸다면 이런 꼴로 나타내어진다.

일반화

 

[min_val,n],[min_val,n+1]....[min_val,max_val] => max_val-n+1개

[min_val+1,n],[min_val+1,n+1]....[min_val+1,max_val]

...

[n-1,n],[n-1,n+1] ....[n-1,max_val]

[n,n+1],[n,n+2] ...[n,max_val]

위의 수열(?) 의 갯수를 세어주면 밑과 같은 식이 도출된다.

총 갯수 : (max_val-n+1) *  (n-min) +  (max_val-n) 

               가로                세로        마지막 항

---

# Brute Force

def solve():
    L = int(input())
    arr =list(map(int,input().split()))
    N = int(input())
    arr.sort()
    pre=0
    
    for num in arr:
    	#같다면,좋은 구간이 있을 수 없다.
        if num==N:
            return 0
        if num>N:
        	#정렬된 상태이므로, min_val = pre +1
            min_val=pre+1
            #정렬된 상태이므로, max_val = num -1
            max_val=num-1
            break
        #num <N, pre값이 num으로 갱신 되어야한다.
        pre =num
    return (N-min_val)*(max_val-N+1)+max_val-N

print(solve())