문제 개요
음수가 아닌 숫자로 이루어진 리스트와 양의 정수 k가 주어졌을 때, 각 원소의 합이 k로 나누어떨어지는 부분 수열(subsequence) 중에서 가장 큰 합을 구하는 문제입니다.
예를 들어 입력이 nums = [4, 6, 8, 2], k = 2라면 출력은 20이 됩니다. 리스트 전체의 합이 20이고, 20은 2로 나누어떨어지기 때문에 모든 원소를 포함한 부분 수열이 곧 정답이 됩니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 입력 리스트 nums의 전체 합을 계산합니다. (numsSum)
- numsSum을 k로 나눈 나머지(remainder)를 구합니다.
- 나머지가 0이라면 전체 합이 이미 조건을 만족하므로 numsSum을 그대로 반환합니다.
- 리스트 nums를 오름차순으로 정렬합니다.
- 1개부터 전체 길이까지 가능한 모든 원소 조합(combination)을 확인하면서, 각 조합의 합(subSeqSum)을 k로 나눈 나머지가 remainder와 같은지 검사합니다.
- 조건을 만족하는 첫 번째 조합을 찾으면, 전체 합에서 해당 조합의 합을 뺀 값(numsSum − subSeqSum)을 반환합니다. 정렬된 상태에서 작은 조합부터 탐색하므로, 가장 먼저 발견되는 값이 최댓값이 됩니다.
- 모든 조합을 확인해도 만족하는 경우가 없다면 0을 반환합니다.
구현 예제
from itertools import chain, combinations
class Solution:
def solve(self, nums, k):
numsSum = sum(nums)
remainder = numsSum % k
if remainder == 0:
return numsSum
nums.sort()
for tpl in chain.from_iterable(combinations(nums, r) for r in range(1, len(nums) + 1)):
subSeqSum = sum(tpl)
if subSeqSum % k == remainder:
return numsSum - subSeqSum
return 0
ob1 = Solution()
print(ob1.solve([4, 6, 8, 2], 2))입력
[4, 6, 8, 2], 2
출력
20
동작 원리 설명
핵심 아이디어는 다음과 같습니다. 전체 합을 k로 나눈 나머지가 r이라면, 합을 k로 나눈 나머지가 r인 부분 수열을 제거하면 남은 원소들의 합은 반드시 k로 나누어떨어집니다.
따라서 문제는 "전체 합에서 나머지가 r인 부분 수열의 합을 빼되, 그 합이 최소가 되도록" 하는 문제로 바꿀 수 있습니다. 리스트를 오름차순으로 정렬한 뒤 작은 조합부터 차례로 검사하면, 나머지 조건을 처음으로 만족하는 조합이 곧 합이 가장 작은 조합이므로 결과적으로 최대 합을 얻을 수 있습니다.
단, 이 방식은 모든 조합을 생성하기 때문에 시간 복잡도가 O(2ⁿ)에 가까워 입력 크기가 커지면 비효율적일 수 있습니다. 실무에서는 동적 계획법(DP)을 활용해 각 나머지 값별 도달 가능 여부를 추적하는 O(n·k) 방식으로 최적화할 수 있습니다.