[BOJ] 백준 1059 좋은 구간 Python

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int,input().split()))
target = int(input())
A.sort()

cnt = 0
if min(A) <= target:
    for i in range (0,N-1):
        if A[i] < target and target < A[i+1]:
            for x in range (A[i]+1,A[i+1]-1):
                for y in range (x+1,A[i+1]):
                    if x <= target and target <= y:
                       cnt += 1
                    else:
                       continue
        else:
            continue
else:
    for x in range (1,min(A)-1):
        for y in range (x+1,min(A)):
            if x <= target and target <= y:
                cnt += 1
            else:
                continue

print(cnt)

아이디어로는, 처음에 먼저 집합 S의 갯수를 받은 뒤, 그에 따라 S의 각 원소를 받습니다.
그 뒤, 찾고자 하는 target의 위치를 받아주겠습니다. (문제의 setting)

 

제일 중요한 것은,이 집합 S의 minimum과 target의 대소관계입니다.
(아마 문제에서, 1<= n <= max(S)로 준 것은 이런 부분에서의 제약이 되겠습니다.)

케이스를 나눠서

I) S의 minimum 값이 target보다 작다면, target은 S의 각 원소 사이사이에 존재하고 있는 상황
II) S의 minimum 값이 target보다 크다면, target은 1과 min(S)사이에 존재하고 있는 상황

I) S의 어떤 원소와 원소 사이에 존재하는지 그 값들을 찾은 뒤, 그 안에서의 좋은 구간 탐색을 진쟁

II) 바로 좋은 구간 탐색을 진행

이렇게 해주면 되겠습니다.