[인프런] 수들의 조합

문제

• n개의 정수와 k개를 뽑을 때, 임의의 정수 m의 배수인 갯수가 몇개 있는가

solution1. combination lib 사용

from itertools import combinations

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

for com in combinations(nums, k):
    if sum(com) % m == 0:
        cnt += 1

print(cnt)

solution2. dfs

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


def dfs(level, start, sum):
    global cnt
    if level == k:
        if sum % m == 0:
            cnt += 1

    else:
        for i in range(start, n):
            dfs(level + 1, i + 1, sum + nums[i])

    return cnt


print(dfs(0, 0, 0)

• list를 생성하여 주어진 자연수 배열을 list에 할당
• 노드의 level, 노드의 시작점(조합은 반복문의 시작점이 필요하다), 원소의 합. 세개의 인자를 받는 dfs 함수를 생성한다.