[인프런] 수들의 조합

---

문제설명

N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수는 몇개가 있는지 출력해라. 예를 들어, 5개의 숫자 2 4 5 8 12 가 주어지고, 3개를 뽑은 조합의 합이 6의 배수인 조합을 찾으면, 4+8+12, 2+4+12로 2가지가 있다.

입력조건

• 첫 줄에 정수의 개수 N(3 <= N <=20)과 임의의 정수 K(2 <= K <= N)가 주어진다.
• 둘째 줄에는 N개의 정수가 주어진다.
• 셋째 줄에 M이 주어진다.

출력조건

• 총 가지수를 출력한다.

사고과정

• 조합을 구하기 위해 상태트리를 만들어 DFS로 조합 경우의 수를 완전 탐색한다. 그리고 하나씩 조합을 탐색할 때마다 같이 실시간으로 원소 누적합을 계산한 후 M으로 나누었을 때 0으로 떨어지면 카운트해준다.

풀이

n, k = map(int, input().split())
arr = list(map(int, input().split()))
m = int(input())
cnt = 0

def dfs(L, s, sum_val):
    global cnt
    if L == k:
        if sum_val % m == 0:
            cnt += 1
    else:
        for i in range(s, n):
            dfs(L+1, i+1, sum_val+arr[i])

dfs(L=0, s=0, sum_val=0)  # res의 인덱스, arr의 인덱스, 누적합
print(cnt)