백준 1059 : 좋은 구간 ( Python )

문제 링크

📌 사용 알고리즘 : 정렬 , brute forcing

N 을 포함하는 특정 구간의 개수를 구하면 되는 문제입니다.

먼저 입력받은 리스트를 오름차순으로 정렬한다음에

for i in range(1,len(L)):
    if L[i-1]<N<L[i]:

이 조건에 맞는 식을 구해주면 됩니다.

공식을 유도해서도 풀 수 있지만 모든 구간의 경우의 수를 직접 구해주었습니다.
이중 반복문을 통해 해결할 수 있습니다.

def query(start,end , N):
    cnt = 0
    for i in range(start+1 ,N+1):
        for j in range(N, end):
            if i==j: continue
            cnt+=1
    return cnt

특정 구간에 포함된다면 시작점보다 항상 1 커야하고 끝점보다 1 작아야 합니다.
따라서 for 문의 파라미터에 주의해야 합니다.
이 때 구간의 크기가 1이면 안되기 때문에 i==j 일경우는 제외해야합니다.

개인적으로 반례 찾기가 까다로웠습니다.

"""
1
1000
1
    
정답: 998  
    
4
5 6 7 8
1

정답: 3
"""

길이가 1 이거나 N 이 리스트의 최소값보다 작을때는

ans = query(0 , L[0] ,N )

쿼리함수의 파라미터에 시작점을 0 으로 잡고 끝점을 L[0] 으로 잡아주면 됩니다.

📌 코드

import sys,math
input=sys.stdin.readline
from functools import lru_cache
from collections import deque
LMI=lambda:list(map(int,input().split()))
LMS=lambda:list(map(str,input().split()))
MI=lambda:map(int,input().split())
I=lambda:int(input())
GI=lambda x:[ LMI() for _ in range(x) ]
GS=lambda x:[ LMS() for _ in range(x) ]
V=lambda x,y:[ [False]*y for _ in range(x) ]

def query(start,end , N):
    cnt = 0
    for i in range(start+1 ,N+1):
        for j in range(N, end):
            if i==j: continue
            cnt+=1
    return cnt

length=I()
L=sorted(LMI())
N = I()
ans = 0
visited = False
for i in range(1,len(L)):
    if L[i-1]<N<L[i]:
        ans = query(L[i-1] , L[i] , N)
        visited = True
        break
if not visited:
    ans = query(0 , L[0] ,N )
print(ans)