Best Sightseeing Pair(Array,Dynamic Programming)

https://leetcode.com/problems/best-sightseeing-pair/description/?envType=daily-question&envId=2024-12-27

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 * 104
• 1 <= values[i] <= 1000

역시나 DP..

문제 이해는 쉬우나 DP인만큼 뭔가를 Memoization 하면서 코드를 짜야하는데 그걸 어떻게 설정할 지 감이 잘 잡히지가 않는다.

 

크흠...

 

1. Python

 

일단 뭔가 막가파로 코드를 짜봤다. 역시나 코드는 돌아가지만 무지막지만 Time complexity때문에 Time Exceed;;;

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        ans = 0
        for i in range(1,len(values)):
            ans = max(ans,values[0]+values[i]-i,self.maxScoreSightseeingPair(values[i:]))
        return ans

 

이건 내가봐도 function CALL이 넘 많아서 되려나 싶긴했다..

 

위 코드는 O(N^2)가 부쩍 넘어가서 매우 비효율적이라고 한다.

 

그래서 답지를 봤는데, 답안 코드도 내꺼랑 크게 다르지 않지만 이건 O(N)라서 시간효율은 엄청나게 좋다.

 

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        ans = 0
        max_val = values[0]
        for i in range(1,len(values)):
            ans = max(ans,max_val+values[i]-i)
            max_val = max(max_val,values[i]+i)

        return ans

 

깔끔하다.. 수학적으로 생각하면 어찌보면 당연한 풀이인데 참.. 벽을 째끔 느꼈다

 

위 개념만 잘 이해했다면 이제 C,C++ 풀이는 누워서 떡먹기..이지만! 답지를 봤다는 자괴감이 좀 든다 ㅠ

 

그래도 뭐 어쩌나.. 한 20분 정도 생각해도 진전이 없으면 답지를 보는 게 낫긴 하다.

 

체력측면에서나 스트레스관리 측면에서..ㅎㅎ

 

아오!

 

 

2. C

int max(int a, int b){
    return a>b?a:b;
}

int maxScoreSightseeingPair(int* values, int valuesSize) {
    int ans = 0;
    int* dp = (int*)malloc(valuesSize*sizeof(int));
    dp[0] = values[0]; // max value until 0th index (values[index]+index)

    for(int i=1;i<valuesSize;i++){
        ans = max(ans,dp[i-1]+values[i]-i);
        dp[i] = max(dp[i-1],values[i]+i);
    }
    return ans;
}

 

3. C++

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int ans = 0;
        int max_val = values[0];

        for(int i=1;i<values.size();i++){
            ans = max(ans,max_val+values[i]-i);
            max_val = max(max_val,values[i]+i);
        }

        return ans;
    }
};

 

원리만 알면 수월허다..!