알고리즘/BOJ
[BOJ] 10167번: 금광
BaaaaaaaaaaaaaaaaaaaaaaarkingDog
2019. 12. 2. 11:40
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초 가까이 걸렸네요.