n개의 요소를 가진 배열이 있다고 가정해 보겠습니다. 이 배열에는 각 책의 평점이 담겨 있습니다. 우리의 목표는 다음 조건을 만족하면서 모든 책을 구입할 때 드는 최소 비용을 구하는 것입니다.
- 각 책의 비용은 최소 1달러 이상이어야 합니다.
- 어떤 책의 평점이 인접한(왼쪽 또는 오른쪽) 책보다 높다면, 해당 책의 비용 역시 인접한 책보다 높아야 합니다.
문제 예시
예를 들어 평점 배열이 [1, 3, 4, 3, 7, 1]과 같이 주어졌다고 해봅시다. 이 경우 정답은 10이 됩니다. 실제 비용 계산은 1 + 2 + 3 + 1 + 2 + 1 = 10이기 때문입니다.
해결 접근 방식
이 문제를 효율적으로 해결하려면 LtoR과 RtoL이라는 두 개의 배열을 만들고, 모든 값을 1로 초기화한 뒤 아래 단계를 수행해야 합니다.
- 왼쪽에서 오른쪽으로 순회: LtoR 배열을 채우되, 주어진 배열에서 바로 앞 요소의 평점과 비교하여 값을 갱신합니다. 이때 뒤에 오는 요소의 평점은 고려하지 않습니다.
- 오른쪽에서 왼쪽으로 순회: RtoL 배열을 채우되, 마찬가지로 바로 앞(즉, 오른쪽) 요소의 평점과 비교하여 값을 갱신합니다.
- 최종 결과 계산: LtoR과 RtoL 두 배열의 i번째 위치 값 중 더 큰 값을 선택하여 결과에 모두 더합니다.
C++ 구현 코드
#include<iostream>
using namespace std;
int getMinCost(int ratings[], int n) {
int res = 0;
int LtoR[n];
int RtoL[n];
for(int i = 0; i<n; i++){
LtoR[i] = RtoL[i] = 1;
}
for (int i = 1; i < n; i++)
if (ratings[i] > ratings[i - 1])
LtoR[i] = LtoR[i - 1] + 1;
for (int i = n - 2; i >= 0; i--)
if (ratings[i] > ratings[i + 1])
RtoL[i] = RtoL[i + 1] + 1;
for (int i = 0; i < n; i++)
res += max(LtoR[i], RtoL[i]);
return res;
}
int main() {
int ratings[] = { 1, 6, 8, 3, 4, 1, 5, 7 };
int n = sizeof(ratings) / sizeof(ratings[0]);
cout << "Minimum cost is: " << getMinCost(ratings, n);
}실행 결과
Minimum cost is: 15
위 예제에서 입력 배열 {1, 6, 8, 3, 4, 1, 5, 7}에 대해 프로그램은 최소 비용으로 15를 출력합니다. 이 알고리즘은 배열을 세 번 선형 순회하므로 시간 복잡도는 O(n), 추가 배열 두 개를 사용하므로 공간 복잡도 역시 O(n)입니다.