정수 배열 nums가 주어졌을 때, 배열 요소들의 합이 3으로 나누어떨어지는 경우 중 가능한 최대 합을 구하는 문제입니다.
예를 들어 입력이 [3, 6, 5, 1, 8]이라면 출력은 18이 됩니다. 이는 부분 수열 [3, 6, 1, 8]을 선택했을 때 합이 18이 되고, 18은 3으로 나누어떨어지기 때문입니다. 만약 5까지 포함하면 합이 23이 되어 3으로 나누어떨어지지 않으므로 제외해야 합니다.
문제 해결 접근 방식
이 문제는 동적 계획법(Dynamic Programming)을 활용하여 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 요소를 처리할 때마다 '현재까지의 누적 합을 3으로 나눈 나머지'별로 최대 합을 추적하는 것입니다.
알고리즘 단계
- n := nums 배열의 크기
- (n + 1) × 3 크기의 2차원 배열 dp 생성 — dp[i][j]는 i번째 요소까지 고려했을 때 합을 3으로 나눈 나머지가 j인 최대 합을 의미합니다.
- 초기값 설정: dp[0][0] := 0, dp[0][1] := -inf(도달 불가능), dp[0][2] := -inf
- i를 1부터 n까지 반복:
- x := nums[i - 1]
- j가 0부터 2까지: dp[i][j] := dp[i-1][j] (이전 상태 복사)
- j가 0부터 2까지:
- k := (x + j) mod 3
- dp[i][k] := max(dp[i][k], dp[i-1][j] + x) — 현재 요소 x를 추가했을 때 더 큰 값 선택
- dp[n][0] 반환 — 나머지가 0인 경우가 곧 3의 배수 합의 최댓값
C++ 구현 코드
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
int n = nums.size();
int dp[n+1][3];
dp[0][0] = 0;
dp[0][1] = INT_MIN;
dp[0][2] = INT_MIN;
for(int i = 1; i <= n; i++){
int x = nums[i-1];
for(int j = 0; j < 3; j++)dp[i][j] = dp[i-1][j];
for(int j = 0; j < 3; j++){
int k = (x + j) % 3;
dp[i][k] = max(dp[i][k],dp[i-1][j] + x);
}
}
return dp[n][0];
}
};
main(){
vector<int> v = {3,6,5,1,8};
Solution ob;
cout << (ob.maxSumDivThree(v));
}입력
[3,6,5,1,8]
출력
18
복잡도 분석
- 시간 복잡도: O(n) — 각 요소에 대해 상수 개수(3개)의 나머지 상태만 갱신하므로 선형 시간에 해결됩니다.
- 공간 복잡도: O(n × 3), 즉 O(n) — 2차원 DP 테이블을 사용하지만, 실제로는 각 단계에서 이전 행만 참조하므로 1차원 배열 3칸짜리 DP로 공간을 O(1)까지 최적화할 수도 있습니다.
이처럼 나머지 연산의 특성을 활용한 DP 테이블 설계는 '특정 배수 조건을 만족하는 최대/최소 합' 유형의 문제에 널리 응용될 수 있는 강력한 기법입니다.