1014. Best Sightseeing Pair
https://leetcode.com/problems/best-sightseeing-pair/
문제
풀이
예시
최대값을 구하는 문제에서 최적화를 하려면 이전 최대값과 현재 계산값과 비교하면서 진행하면 된다.
예를 들어보자
values = [5,1,3,8,6]에서 (i < j)라는 조건에서 values[i] + values[j]의 최대값을 구해보자
직관적인 방법으로 BruteForce로 n^2 시간복잡도로 구할 수는 있을 것이다.
하지만 이전 최대값을 알고 현재값을 더한 후 이전값과 비교해서 크다면 갱신해주는 방법으로 하면 된다.
j = 1일 때 prev_max = 5이고 현재 1이므로 6
j = 2일 때 prev_max = 5이고 현재 3이므로 8
j = 3일 때 prev_max = 5이고 현재 8이므로 13(prev_max보다 현재값이 더 크므로 prev_max=8)
j = 4일 때 prev_max = 8이고 현재 6이므로 14
즉 최적화를 통해서 n이라는 시간복잡도로 구할 수 있다.
문제에서 적용해보자
문제에선 비슷하지만 거리라는 변수가 존재한다. for문을 돌수록 거리는 멀어지므로 prev_max라는 값은 점점 작아진다. 이것을 고려하여 표를 만들어보자
prev_max는 i가 증가할수록 감소한다. 감소된 prev_max와 현재 values[i]값과 비교해서 크면 갱신한다. 또한 최대값도 계속 갱신한다.
i가 증가할수록 prev_max는 1씩 감소하게 하고 ans값을 찾아준다. 또한 prev_max와 현재 values를 비교해서 갱신한다.
결과
