17251 힘 겨루기

N 제한을 봤을 땐 O(N)에 해결해야 하는 문제다. 각 위치에서 최댓값만 알면 된다. 기준을 나눴을 때 left에서의 최댓값 sleft, 오른쪽에서의 최댓값 sright 배열에 최댓값만을 넣을 수 있다.

sleft는 왼쪽부터 탐색을 진행하면서 최댓값을 교체해가면서, 반대로 sright는 오른쪽부터 탐색을 진행하면서 최댓값을 교체할 수 있다. 그리고 채워진 배열을 비교하면 시간복잡도 O(N)으로 해결할 수 있다

 

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

https://github.com/surinoel/boj/blob/master/17251.cpp