Algorithm (PS)

[백준] 2283 구간자르기 (Python/파이썬) - 부분합 & 투포인터

minjiwoo 2023. 1. 17. 22:31
728x90

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

 

2283번: 구간 자르기

1번째 줄에 정수 N, K(1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000)가 주어진다. 2~N+1번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다. 양 끝점의 위치는 0 이상 1,000,000 이하의 정수이다.

www.acmicpc.net

 

n, k = map(int, input().split())
array = [0] * 1000002 # 1 ~ 100001 까지 저장 

for i in range(n):
    a, b = map(int, input().split())
    array[a+1] += 1
    array[b+1] -= 1

for i in range(1, 1000002):
    array[i] += array[i-1]

flag = False
left = 0
right = 0
t = 0
while True:
    if t < k:
        right += 1
        t += array[right]
    elif t > k:
        left += 1
        t -= array[left]
    else:
        flag = True
        break
    if right == 1000001:
        break
    
if flag:
    print(left, right)
else:
    print(0, 0)
728x90