[platinum1] [풀이안봄,분류확인] 1665 화물열차

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

이 문제는 딱 보자마자 세그먼트 트리인줄 알고 세그먼트 트리면 다음을 기악하려고 분류를 확인했는데 세그는 아니였고.. 차분배열 트릭? 이라는 게 있었는데 이게 뭔진 찾아보지 않았고  아이디어가 떠올라서 풀 수 있었다. 분류에는 누적합이 있었지만 내가 알던 그 누적합은 아니라 딱히 도움은 되지 않았던 것 같다 ㅜ

 

이 문제를 풀때 가장 중요했떤 것은 열차B를 움직일때 B안의 컨테이너들을 각각 따로따로 생각한다는 것이다. 열차 A안의 컨테이너들을 a1, a2, a3... B안의 컨테이너들을 b1,b2... 라고 한다.   A의 컨테이너가 1000개, B의 컨테이너가 1000개이면  컨테이너들이 만나는 조합은 1000 * 1000 (b의 모든 컨테이너 들 b1~b1000가 각각 a1~a1000 까지 만나는 경우) 이고,  B를 움직일 때 만날때 이벤트가 발생하는(겹치는 구간이 증가 or 감소 or 증가 정지 or 감소 정지 ) 지점들도 k * 100만 (k는 상수) 가 될 것이다. 

l1만큼 B를 이동했을 때 a1과 b1가 만나고  b1이 A와 겹치는 구간이 증가하기 시작한다.

 

B를 l2만큼 이동하면 b1의 모든 부분이 a1안에 들어가게 되어 더이상 B를 움직여도 겹치는 구간이 증가하지 않는다.

 

 

B를 l3만큼 이동하게 되면 이제 부터는 B를 이동시키면 b1이 A와 겹치는 구간이 감소하기 시작한다.

l4만큼 이동하게 되면 이제 b1이 a1에서 완전 빠져나가 더이상 이동해도 감소하지 않는다.

즉 A의 한 컨테이너가 B의 컨테이너와 만나 이벤트가 발생하는 지점은 l1, l2, l3, l4 만큼 이동할 때의 4지점이다. (증가 시작, 증가 stop, 감소 시작,  감소 stop)

그렇다면 A컨테이너 1000개 B컨테이너 1000개이면 지점들은 4000000(400만개) 일 것이다.

 

내가 처음에 해맨 부분은 이렇게 만든 400만개에 대해 각 B의 컨테이너에서 겹치는 구간의 총합을 계산한다는 것이였다. 

b1이 모든 지점에서 겹치는 부분을 구한다. 그 후 b2 가 각 지점에서 겹치는 부분을 b1의 수치에 누적합으로 더한다. b3,b4,...b1000도 누적합으로 모든 지점에 대해 더한다... 

이렇게 하면 확실히 구할 수는 있겠지만 400만개 * 1000  = 40억의 시간복잡도로 TLE가 발생할 것이다.

 

 

그래서 내가 생각한 방법은 각 컨테이너마다 모든 지점들에 대해 계산하지 말고, 다음과 같이 생각했다. 

status[] 라는 배열을 일단 둔다.

b1컨테이너가 a의 컨테이너들과 만나는 지점들은 최대 4000개이다. (p1,p2,p3...p4000이라 하자) . p1에서 겹치는 구간이 증가한다면 status[p1] ++ , p2 가 감소시작한다면 status[p2]--, p3가 증가를 중단한다면 status[p3] -- . p4가 감소를 중단한다면 status[p4]++ 를 하였다.  이렇게 하면 각 지점들마다 얼만큼 증가하고 감소하는지 상태를 알 수 있다.

만약 b2에서 p1에서 감소하기 시작한다면 status[p1]-- , 이런 식으로 다른 컨테이너들에서도 지점들이 중첩된다면 여기에 누적해 상태를 더할 수 있다. 

이를테면 b1,b2에서 p1에서 증가하고, b3가 p1에서 감소한다면 status[p1] = 3 - 1 = 2 가 된다.  status[p1] = 2 이면 다른 지점까지는 한칸 이동할 때마다 겹치는 구간이  +2 씩 늘어나게 된다.

위의 경우를 보자. B가 5만큼 이동하는 지점 p1에서 b1는 a2와 만나고 b2는 a3와 만난다. 

이때 b1은 a2와 겹치기 직전이므로 증가 시작이므로 status[p1] ++ , b2는 a3와 만나기 직전이므로 마찬가지로 증가시작이므로 status[p1]++ 해서 status[p1] = 2 가 된다.     즉 status는 어떤 컨테이너가 누구와 만나는지를 보는게 아니라 B전체를 움직인 지점에서 전체적인 status를 확인하는 기능이다.

 

 

 

구현 순서는 우선 b1이 A와 만나는 지점 대락 4000개에 대해 status[p1] , status[p2]...status[p4000] 까지 구하고, 

그 다음으로 b2가 A와 만나는 지점 4000개에 대해 status[p4000], status[4001] ,... status[8000] 까지 구한다. (위의 그림에서의 p1과 같이 b1에서의 지점과 중복될 수도 있다.)   b3,b4... b1000까지 반복하면 status는 최대 400만개의 배열로 만들어질 것이다.

 

 

그런데 당연하게도 지금까지 구한 p는 오름차순이 아닌 뒤죽박죽이다. p를 오름차순으로 정렬을 해야 한다. (이부분이 시간복잡도의 대부분을 차지)

그후 p1,p2...p4000000까지 순차적으로 status를 확인하면서 누적합을 더해나가면 답을 구할 수 있다.

 

p1,p2,p3... 는 오름차순으로 정렬시키고,

 

status[p1] 이 3이면 다음구간 p2일때까지 기울기 3으로 총합이 증가한다. p2에서 status는 -2이고, status의 누적으로 3-2 = 1 ,  1만큼 p3일때까지 증가한다. 이런 식으로 p1,p2...p3 를 지나면서 겹치는구간 총합의 최댓값을 구하면 된다. 

 

 

이 문제의 또다른 어려운 점은 메모리다. 메모리가 너무 빡빡하다. p의 범위는 0~10억까지 나올 수 있어서 Map<p, p에서의 status> 로 구하려 했으나 400만개의 key-value쌍으론 메모리 초과가 되었다. 그래서 생각해낸게 그냥  p를 정렬하고

status[0] = p1,

status[1] = p2,

status[2] = p3... 

 

list[i] = i번째의 p의 좌표로 설정

 

list[0] = p1,

list[1] = p2...

list[4000000] = p400000 

 

    p에서의 status를 조회하고 싶으면  list에서 이진탐색을 통해 p일때의 인댁스 i를 알아내어 status[i] 를 조회하는 식으로 진행하였다. Map을 사용한다면 O(1)이였지만 이 경우엔 O(log _2 4000000) = 22정도의 시간복잡도였다.  

따라서 초기에 400만개의 p를 정렬할 때 O(400만 * log(400만)) , 후에 status의 누적합을 구할 때 이분탐색을 통해 status를 조회해야 하므로, 마찬가지로 O(400만 * 22)  총합  O(1억6000만)... 의 상당한 시간복잡도가 나온다,.

시간복잡도 거의 턱걸이로 통과한것 같다...