Best Sightseeing Pair 문제
You are given an integer array values where values[i] represents the value of the ith sightseeing spot. Two sightseeing spots i and j have a distance j - i between them.
The score of a pair (i < j) of sightseeing spots is values[i] + values[j] + i - j: the sum of the values of the sightseeing spots, minus the distance between them.
Return the maximum score of a pair of sightseeing spots.
Example 1:
Input: values = [8,1,5,2,6]
Output: 11
Explanation: i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
Example 2:
Input: values = [1,2]
Output: 2
Constraints:
2 <= values.length <= 5 * 10^4
1 <= values[i] <= 1000
체크해야할 점
- brute force로 풀면 n^2 이다. 10억 연산이 훌쩍 넘어가므로 해당 방법으로 풀면 안된다.
- 결국엔 이전에 구한 답과 계속 반복해가면서 갱신하는 kadene 방법을 사용해야 한다.
문제 해결 방법
이런 다이나믹 프로그래밍 문제는 점화식을 구하는 것이 가장 중요하다.
예시를 통해 점화식을 구체화 해보자.
[7,2,6,6,9,4,3] 가 주어졌다고 가정해보자.
먼저 7 2 를 선택한 후 (7 + 2) - distance 는 8 이다.
그 후 우리가 선택할 수 있는 선택지는 7 6 or 2 6 존재한다.
7 6(11) 이 2 6(7) 보다 더 크다. 이제 우리는 위에서 구한 8과 11을 비교해준다.
max_answer를 11로 갱신시켜준다.
이렇게 계속 진행하다보면 의문이 생길 것이다. 과연 계속 7부터 시작하는 것이 맞을까?
여기서 우리는 distance를 주목해야 한다.
결국 7이라는 숫자도 distance가 커지면 커질수록 점점 작은 숫자가 된다.
때문에 우리는 7 - distance 보다 같거나 큰 숫자를 찾게 된다면 갱신해야 한다.
위의 예시에서는 7이라는 숫자는 6을 만나면서 효력을 잃는다.
생각해보면 아래와 같은 수식의 부등호가 바뀌는 시점이 존재한다.
(prev_value-until_curr_dist)+next_value-distance <= curr_value+next_value-distance
note that
prev_value = 7
until_curr_dist = 2
curr_value = 6
위의 수식에서 필요한 부분만 가져오자.
즉 우리는 아래와 같은 상황만 신경쓰면 된다는 것이다.
prev_value-until_curr_dist <= curr_value
즉 이전까지 가장 큰 수는 계속해서 효력을 잃게되고 어느 임계점에 도달하게 되면 prev_value-until_dist 보다 curr_value가 크게되면 prev_value를 curr_value로 바꿔주는 것이다.
파이썬 코드로 구현하면 다음과 같다.
class Solution:
def maxScoreSightseeingPair(self, values: List[int]) -> int:
prev_idx = 0
prev = values[prev_idx]
answer = float('-inf')
for i in range(1, len(values)):
curr = values[i]
distance = i - prev_idx
temp = prev + curr - distance
answer = max(answer, temp)
if values[i] >= prev - distance:
prev_idx = i
prev = values[prev_idx]
return answer아래와 같은 점화식으로 푼 경우(접근 방식은 일치하되 풀이 방법이 다른 경우)
Suppose we have a = [8,1,5,2,6]
create a dp = [0, 0, 0, 0] where dp[i] represents the best possible answer if we consider all pairs forming with a[i] (like i = 3 then it will be (0, 3),(1, 3), (2, 3))
For d[0] it will be 0
For d[1] it will be a[0] + a[1] + 0 - 1
For d[2] it will be max((a[0] + a[2] + 0 - 2), (a[1] + a[2] + 1 - 2))
For d[3] it will be max((a[0] + a[3] + 0 - 3), (a[1] + a[3] + 1 - 3), (a[2] + a[3] + 2 - 3))
For d[4] it will be max(a[0] + a[4] + 0 - 4), (a[1] + a[4] + 1 - 4), (a[2] + a[4] + 2 - 4), (a[3] + a[4] + 3 - 4))
Rewriting above by taking about common term out of max() function
For d[0] it will be 0
For d[1] it will be a[0] + 0 + a[1] - 1
For d[2] it will be max((a[0] + 0), (a[1] + 1)) + a[2] - 2
For d[3] it will be max((a[0] + 0 ), (a[1] + 1), (a[2] + 2)) + a[3] - 3
For d[4] it will be max(a[0] + 0 ), (a[1] + 1), (a[2] + 2), (a[3] + 3 )) + a[4] - 4
For a minute lets ignore the part outside the max function and drop it for now, So make a new series and call it dp
For dp[0] it will be 0
For dp[1] it will be a[0] + 0
For dp[2] it will be max((a[0] + 0), (a[1] + 1))
For dp[3] it will be max((a[0] + 0 ), (a[1] + 1), (a[2] + 2))
For dp[4] it will be max(a[0] + 0 ), (a[1] + 1), (a[2] + 2), (a[3] + 3 ))
Here is the catch
dp[i] = max(dp[i-1], a[i-1] + i - 1)
You can Clearly see this pattern in above dp series
Combining this to d series we can get:
For d[0] it will be 0
For d[1] it will be dp[0]+ a[1] - 1
For d[2] it will be max(dp[1], (a[1] + 1)) + a[2] - 2
For d[3] it will be max(dp[2], (a[2] + 2)) + a[3] - 3
For d[4] it will be max(dp[3], (a[3] + 3 )) + a[4] - 4
풀이
class Solution:
def maxScoreSightseeingPair(self, values: List[int]) -> int:
maxVal = 0
cur = 0
for i in range(1, len(values)):
cur = max(cur, values[i-1]+i-1)
maxVal = max(maxVal, cur+values[i]-i)
return maxVal