새소식

Computer Science/코딩테스트 문제 풀이

⭐⭐⭐⭐[백준] [파이썬] [투 포인터] 2283번: 구간 자르기

  • -

 

투 포인터 문제집 : https://www.acmicpc.net/workbook/view/8709

 

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

 

수직선(數直線) 상에 구간 N개가 있다. 임의의 두 정수 A, B(A < B)를 정하여, 각 구간에서 A와 B 사이에 포함되지 않은 부분을 모두 잘라냈을 때 남는 부분들의 길이의 총합이 K가 되도록 하여라.

1번째 줄에 정수 N, K(1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000)가 주어진다.

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

두 정수 A, B를 출력한다. 조건을 만족하는 A, B가 존재하지 않으면 “0 0”을 출력한다.

조건을 만족하는 A, B가 여러 개 존재할 때는 A가 가장 작은 경우를 출력한다. 그것도 여러 개 존재할 때는 B가 가장 작은 경우를 출력한다.

4 25 0 10 3 15 0 8 3 10
2 9

 

문제 요약:

각 구간에서 A와 B 사이에 포함되지 않은 부분을 모두 잘라냈을 때 남는 부분들의 길이의 총합이 K가 되도록 하여라.

-> 구간 A와 B 사이의 겹치는 구간의 누적합을 구하여랴!!

 

아니 왜 문장을 이렇게 어렵게 쓰는거야~~

 

단순히 보면 그냥, 선들 겹치는 부분 누적합을 구하라는 뜻이다. 그 누적합이 K가 되도록 하는 구간 A와 B를 구하라는 말.

 

나는 처음에 A와 B 사이에 포함되지 않는 부분의 누적합인 줄 알았잖아!!

 

그러면 아주 전형적이고 대표적인 투포인터 문제이며 

겹치는 구간을 미리 더해준 arr를 먼저 고려하여 만들어준 후 투 포인터를 진행하면 되겠다. 

 

if __name__=="__main__": N,K = map(int, input().split()) max_num = 1_000_000 + 1 array = [0]*max_num for _ in range(N): start,end = map(int, input().split()) # 선의 위치 겹치는 부분은 += 1씩 증가한다. for i in range(start, end): array[i] += 1 flag = False left, right = 0,0 add = 0 while left<=right<max_num: if add == K: # 나머지 누적합이 목표값이 되었을 때 flag = True break elif add < K: add += array[right] # 오른쪽 화살표 오른쪽으로 이동 right += 1 elif add > K: add -= array[left] # 왼쪽화살표 오른쪽으로 이동 left += 1 if flag: print(*[left, right]) else: print(*[0,0])

 

 

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.