문제링크
Leetcode #1262. Greatest Sum Divisible by Three
풀이방법
이 풀이는 해당 문제의 Discuss를 참고했다. 총 두 가지 방법을 남기고자 한다.
풀이 #1
생각하기는 쉽지 않지만, 생각하면 쉬운 방법이다. 배열 내 모든 원소의 합을 구하고 그걸 3으로 나누었을 때 경우에 따라 진행한다.
- sum % 3 == 0 👉 그 값을 리턴
- sum % 3 == 1 👉 원소 내 조합 중 나머지가 1인 합이 가장 작은 조합의 합을 뺌
- sum % 3 == 2 👉 원소 내 조합 중 나머지가 2인 합이 가장 작은 조합의 합을 뺌
그럼 여기서 나머지가 1, 2인 합이 가장 작은 조합의 합은 어떻게 구할까?
이것도 여러 케이스를 생각해본다. 3으로 나눴을 때 나머지는 0, 1, 또는 2이다. 모든 수는 이 세 케이스로 구분할 수 있다! 나머지가 1, 2인 합이 가장 작은 조합의 합을 구한다는 목적으로 배열 내 원소들을 돌 때 그 케이스를 다음과 같이 나눌 수 있다.
- num % 3 == 0 👉 나머지가 1, 2인 조합 합에 num을 더하면 그 조합 합이 커질 뿐이다. 따라서 아무것도 하지 않는다.
- num % 3 == 1 👉 나머지가 1인 조합 합 + num을 하면 나머지가 2가 된다(3n + 1 + 3k + 1 = 3(n + k) + 2). 이 값이 원래 나머지가 1인 조합 합보다 작을 수 있으므로 비교해 작은 값을 나머지가 2인 조합 합에 저장한다. 그리고 나머지가 1인 조합 합 값과 num을 비교해 더 작은 값을 나머지가 1인 조합 합에 저장한다.
- num % 3 == 2 👉 나머지가 2인 조합 합 + num을 하면 나머지가 1이 된다(3n + 2 + 3k + 2 = 3(n + k + 1) + 1). 이 값이 원래 나머지가 2인 조합 합보다 작을 수 있으므로 비교해 작은 값을 나머지가 1인 조합 합에 저장한다. 그리고 나머지가 2인 조합 합 값과 num을 비교해 더 작은 값을 나머지가 2인 조합 합에 저장한다.
이해가 어려울 수 있다. [2,6,2,2,7]가 있다고 생각하자. 총 합은 19이고 3으로 나눴을 때 나머지는 1이다. 만약 단순히 나머지가 1인 조합 합과 num을 비교하는 연산만 진행했다면 담은 12(19-7)이 될 것이다. 하지만 [나머지가 2인 조합 합 + num을 하면 나머지가 1이 된다. 이 값이 원래 나머지가 2인 조합 합보다 작을 수 있으므로 비교해 작은 값을 나머지가 1인 조합 합에 저장한다.] 이 과정을 통해 나머지가 1인 조합 = 나머지가 2인 조합(2) + num(2)를 해 4를 갖게된다. 따라서, 15라는 맞는 결과를 낼 수 있다.
코드
public int maxSumDivThree(int[] nums) {
int totalSum = 0;
int leftTwo = NO_SUCH_NUM;
int leftOne = NO_SUCH_NUM;
for (int num : nums) {
totalSum += num;
if (num % 3 == 1) {
leftTwo = Math.min(leftTwo, leftOne + num);
leftOne = Math.min(leftOne, num);
}
else if (num % 3 == 2) {
leftOne = Math.min(leftOne, leftTwo + num);
leftTwo = Math.min(leftTwo, num);
}
}
int result = 0;
switch (totalSum % 3) {
case 0:
result = totalSum;
break;
case 1:
result = totalSum - leftOne;
break;
case 2:
result = totalSum - leftTwo;
break;
}
return result;
}풀이 #2
DP를 이용한다. 사실 아이디어는 풀이 #1과 같다. 모든 수를 %3 했을 때 경우의 수는 0, 1, 2뿐이라는 아이디어를 이용한다. 이 문제에서 묻는 것은 가장 "큰" 합이기 때문에 작은 수는 저장하지 않고 당시에 가장 큰 수를 저장한다. dp[i]의 의미는 나머지가 i인 합 중 가장 큰 합이다. 배열 내 모든 원소를 돌며 나머지가 i인 수를 크게크게 갱신한다. 이 연산 시 필요한 건 모든 수가 아니라 나머지가 0, 1, 2인 합 중 가장 큰 합이다.
코드
public int maxSumDivThreeDP(int[] nums) {
int[] dp = new int[3]; // dp[i]: ㄴㅏ머지가 i인 수 중 가장 큰 수
for (int num : nums) {
for (int i : Arrays.copyOf(dp, dp.length)) {
dp[(i + num) % 3] = Math.max(dp[(i + num) % 3], i + num);
} // % 3했을 떄, 모든 경우는 나머지가 0, 1, 또는 2이다. 가장 큰 수를 구할거니까 작은 수는 필요없다! 해당 나머지를 갖는 가장 큰 수만 저장!
}
return dp[0];
}