[BOJ] 2283번 - 구간 자르기

[BOJ] 2283번 - 구간 자르기

문제 푼 방식과 어떻게 풀었는지에 대해 설명하여 보겠습니다.

문제 링크는 다음과 같습니다.

 

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

2283번: 구간 자르기

 

문제 이해

---

처음 문제를 이해한 바로는 N 은 1000까지 K는 10억까지로써, K로 나누어질 수 있는 좌우 부분을 구하라는 문제로 이해하였습니다. 이에 따라 10억까지의 숫자 범위에서 메모리적으로 투포인터로 범위를 구하는 것이 불가능하다 판단하여, 각 경우의 수에 대하여 이분 탐색으로 풀어보려고 하였으나, O(N*K*logK) 이라는 것이 제 생각에 최대였습니다. 

문제에 대한 조건이 아래 추가로 나와있는데 이부분을 늦게 포착하여 푸는데 오래걸렸습니다 ㅠㅠ

 

다시 문제 조건을 보면, 양끝점은 위치는 0~백만입니다. 

백만이라면 위에서 메모리가 부족했다고 판단한 부분을 다시 생각할 수 있는 값이라, 다시 알고리즘을 생각하여보았습니다. (백만이라면 Int형이 백만개 있어도 128mb면 충분)

 

알고리즘

---

위의 구성으로 투포인터로 가능하다고 판단하여 구현하였습니다.

일단 각 숫자 범위일 때 몇개의 구간이 포함되어있는지 Init한 다음에 투포인터로 풀었습니다.

최소값(Left)은 작은 수부터 순서대로 하되, K값보다 클 때까지 Right 값을 옮겼습니다.

1. 최소값 설정

2. K값보다 크거나 같은값이 나올때까지 Right 이동

3. 최소값 범위 확인 후 계산된 값 빼어준다.

4. 2~3반복

 

코드

---

#BOJ 2283번
import sys
input = sys.stdin.readline

#init
answer = [0,0]
n , k = map(int,input().split())
number = [0]*1000001
right ,sum_value = 0 , 0

#input
for _ in range(n) :
    temp = tuple(map(int,input().split()))
    for i in range(temp[0],temp[1]):
        number[i]+=1

#two pointer
for i in range(1000001) : 
    #right 범위 지정
    while sum_value < k and right <= 1000000: 
        sum_value+=number[right]
        right+=1

    if sum_value == k :
        answer = [i,right]
        break
    sum_value-=number[i]

print(*answer)