문제 설명
양의 정수로 구성된 배열 A가 있다고 가정해 보겠습니다. 여기서 A[i]는 i번째 관광 명소의 가치를 나타내며, 두 관광 명소 i와 j 사이의 거리는 j - i입니다. 이때 관광 명소 쌍 (i < j)의 점수는 다음 공식으로 계산됩니다.
A[i] + A[j] + i - j
우리의 목표는 이 점수가 최대가 되는 관광 명소 쌍을 찾는 것입니다. 예를 들어 입력이 [8, 1, 5, 2, 6]이라면 출력은 11이 됩니다. i = 0, j = 2일 때 A[0] + A[2] + 0 - 2 = 8 + 5 + 0 - 2 = 11이 되어 최댓값이기 때문입니다.
접근 방법
이 문제의 핵심 아이디어는 점수 공식을 두 부분으로 분리하는 것입니다.
A[i] + A[j] + i - j = (A[i] + i) + (A[j] - j)
즉, 각 위치 j에 대해 그 이전 위치들에서 나온 (A[i] + i) 값의 최댓값만 추적하면 됩니다. 이렇게 하면 모든 쌍을 일일이 확인하는 O(n²) 방식 대신, 단 한 번의 순회(O(n))로 문제를 해결할 수 있습니다.
다음 단계를 따라 해결할 수 있습니다.
ret := 0, maxVal := 0으로 초기화하고, n := 배열 A의 크기로 설정합니다.
i를 0부터 n - 1까지 반복합니다.
ret := max(ret, maxVal + A[i] - i) — 현재까지의 최대 점수를 갱신합니다.
maxVal := max(A[i] + i, maxVal) — 이후 계산에 사용할 (A[i] + i)의 최댓값을 갱신합니다.
최종적으로 ret을 반환합니다.
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxScoreSightseeingPair(vector<int>& A) {
int ret = 0;
int maxVal = 0;
int n = A.size();
for(int i = 0; i < n; i++){
ret = max(ret, maxVal + A[i] - i);
maxVal = max(A[i] + i, maxVal);
}
return ret;
}
};
main(){
vector<int> v1 = {8, 1, 5, 2, 6};
Solution ob;
cout << (ob.maxScoreSightseeingPair(v1));
}입력
[8,1,5,2,6]
출력
11
복잡도 분석
- 시간 복잡도: O(n) — 배열을 한 번만 순회하면 됩니다.
- 공간 복잡도: O(1) — 추가적인 저장 공간 없이 상수 개의 변수만 사용합니다.