크기가 각각 n과 m(n ≥ m)인 두 개의 배열 nums와 multipliers가 있다고 가정해 보겠습니다. 두 배열은 모두 1부터 인덱싱되며, 초기 점수는 0입니다. 우리는 정확히 m번의 연산을 수행해야 하며, i번째 연산(1-indexed)에서는 다음과 같은 작업을 진행합니다.
- nums 배열의 시작 또는 끝에서 값 x를 하나 선택합니다.
- 점수에 multipliers[i] * x를 더합니다.
- 선택한 값 x를 nums 배열에서 제거합니다.
목표는 m번의 연산을 모두 수행한 후 얻을 수 있는 최대 점수를 구하는 것입니다.
예시
예를 들어 nums = [5,10,15], multipliers = [5,3,2]가 입력으로 주어진다면, 출력은 115가 됩니다.
그 이유는 다음과 같습니다.
- 먼저 끝의 15를 선택하고 5와 곱합니다 → 15 × 5 = 75
- 다음으로 10을 선택하고 3과 곱합니다 → 10 × 3 = 30 (누적 합계: 105)
- 마지막으로 남은 5를 선택하고 2와 곱합니다 → 5 × 2 = 10 (최종 합계: 115)
해결 방법: 동적 계획법(DP)
이 문제는 동적 계획법(Dynamic Programming)을 활용하여 효율적으로 해결할 수 있습니다. 핵심 아이디어는 왼쪽에서 i개, 오른쪽에서 (j - i + 1)개의 원소를 사용했다는 상태를 정의하는 것입니다. 단계별 접근 방법은 다음과 같습니다.
- n := nums의 크기, m := multipliers의 크기로 설정합니다.
- 크기가 m × (m+1)인 2차원 배열 dp를 만들고 0으로 초기화합니다.
- i를 m-1부터 0까지 역순으로 순회하면서:
- j를 i부터 m-1까지 순회하며:
- k := i + m - j - 1 로 현재 사용할 multiplier의 인덱스를 구합니다.
- dp[i][j] = max(nums[i] × multipliers[k] + dp[i+1][j], nums[j-m+n] × multipliers[k] + dp[i][j-1])
즉, 앞쪽에서 값을 선택하는 경우와 뒤쪽에서 값을 선택하는 경우 중 더 큰 값을 저장합니다.
- dp[0]의 마지막 원소를 반환합니다.
구현 코드
아래는 위 알고리즘을 파이썬으로 구현한 예제입니다.
def solve(nums, multipliers):
n, m = len(nums), len(multipliers)
dp = [[0]*m for _ in range(m+1)]
for i in reversed(range(m)):
for j in range(i, m):
k = i + m - j - 1
dp[i][j] = max(nums[i] * multipliers[k] + dp[i+1][j], nums[j-m+n] * multipliers[k] + dp[i][j-1])
return dp[0][-1]
nums = [5,10,15]
multipliers = [5,3,2]
print(solve(nums, multipliers))입력
[5,10,15], [5,3,2]
출력
115
이처럼 동적 계획법을 사용하면 각 단계에서 배열의 앞 또는 뒤에서 값을 선택하는 두 가지 경우를 모두 고려하면서, 최종적으로 얻을 수 있는 최대 점수를 O(m²) 시간 복잡도 안에 효율적으로 계산할 수 있습니다.