[도전 2일차] 세 용액, 버스 노선

문제 1 : BOJ 2473 세 용액

문제 링크

사용 알고리즘 : 투 포인터

 

풀이: 투 포인터를 잘 모른다면 두 용액 문제를 먼저 풀고 오는 것이 좋다.

배열을 정렬하고 시작하자.

먼저 for 문을 이용해서 시작지점을 1부터 n까지 정한다.

시작지점을 s라 한다면 s+1 번째 부터 n번째 범위 안에서 두 용액을 더했을 때 -arr[s] 와 가장 근접한 두 용액을 찾는다.

순서대로 m,e 라 하자. 초기값은 m=s+1, e=n이다.

abs(arr[s]+arr[m]+arr[e]) 가 기존에 구해놓았던 차이보다 작으면 답을 갱신해준다.

배열이 정렬되어 있으므로

arr[s]+arr[m]+arr[e]>0 이면 e-- 해주고 (용액의 합 감소)

arr[s]+arr[m]+arr[e]<0 이면 s++ 한다.  (용액의 합 증가)

 

이렇게 loop 가 끝나면 최종 답이 나온다.

 

*abs(arr[s]+arr[m]+arr[e]) 의 최대값이 30억이므로 차이의 초기값을 1e10으로 설정하자.

 

문제 2: BOJ 10165 버스 노선

문제 링크

 

사용 알고리즘 : 라인 스위핑

 

풀이: 

버스 정류장은 [s,e] 형식으로 주어진다.

이때 우리는 버스 정류장을 2가지 종류로 구분할 수 있다.

출처: 백준

Type A) s<e  1번,2번,4번이 이에 해당한다.

Type B) s>e 3번,5번이 이에 해당한다.

 

먼저 Type A에서만 포함 관계를 판단해보자.

이때 모든 정류장은 s<e 일 것이다. 정류장을 s 오름차순, e 내림차순으로 정렬한다.

그리고 처음부터 훑으면서 e의 최대값을 계속 갱신한다. 이때 정류장의 e가 직전 e의 최대값 이하라면 이 정류장은 '어떤 정류장'에 포함된다. s 오름차순으로 정렬했기 때문에 s 기준으로는 지금까지 살펴본 모든 정류장에 포함되고, e 최대값 이하라는 뜻은 이 정류장을 포함하는 정류장이 존재한다는 것을 의미한다.

이렇게 스위핑하여서 TypeA 에서 '포함되는 정류장'을 판단할 수 있다.

 

Type B도 하나의 처리를 해주면 Type A와 똑같은 방식으로 해결할 수 있다.

그 방법은, 정류장을 저장할 때 e = e+n 하는 것이다. e에 n을 더해준다면 Type B도 Type A 처럼 생각할 수 있다.

 

그럼 이제 Type A, Type B간 포함관계를 판단해보자.

Type A는 n-1 과 0을 동시에 포함하지 않는다.

Type B는 n-1과 0을 동시에 포함한다.

■ 고로, Type A는 Type B를 포함할 수 없다.

 

Type B는 [s,e] (s>e) 이고 [s,n-1] + [0,e]과 동치이다.

만약 Type A 가 type B에 포함된다면 분할된 두 구간 중 하나에 포함될 것이다.

우리는 Type A가 TypeB에 포함되는지만 판단하면 되므로, Type B 중에서 s의 최솟값과 e의 최대값을 구한 후

Type A를 전부 훑으면서 s의 최솟값보다 s가 크거나, e의 최대값보다 e가 작은 정류장은 모두 어떤 Type B에 포함된다고 사료할 수 있다.

 

:D