[BOJ] 10167번: 금광

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

 

주어진 수열에서 연속한 구간의 최대 합 문제를 DP로 해결할 수도 있지만, 수열의 index를 1부터 $N$까지라고 할 때

 

- 1번째 원소를 포함하는 구간 중에서 최댓값을 저장하는 $lmax$

- $N$번째 원소를 포함하는 구간 중에서 최댓값을 저장하는 $rmax$

- 아무 제한 조건 없이 최댓값을 저장하는 $allmax$

 

변수를 가지고 segment tree와 같은 느낌으로 해결할 수도 있습니다.

 

segment tree를 활용할 경우 값의 update를 $O(lg N)$에 처리할 수 있다는 장점이 있기에 이 문제에서 사용하기 적합합니다.

 

일단 좌표압축을 하고, 특정 x좌표를 시작점으로 해 끝까지 가면서 update를 하고 최댓값을 구하는 방식으로 처리할 경우 $O(N^2lgN)$에 해결이 가능합니다.

 

재귀 버전이라 그런지 시간이 2.4초 가까이 걸렸네요.

 

https://github.com/blisstoner/BOJ/blob/master/10167.cpp