[파이썬 알고리즘 문제풀이] - Section6 / 완전탐색 (백트랙킹, 상태트리와 CUT EDGE)-DFS(깊이우선탐색)기초 - 11

수들의 조합

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이 주어집니다.

▣ 출력설명
총 가지수를 출력합니다.

▣ 입력예제 1
5 3
2 4 5 8 12
6

▣ 출력예제 1
2

import sys
# sys.stdin = open("inAA.pyput.text", "rt")

n, k = map(int, input().split())
data = list(map(int, input().split()))
m = int(input())
res = [0] * k

cnt = 0
def DFS(L, start):
    global cnt
    if L == k: #다 뽑았으면 종료조건
        if sum(res) % m == 0:
            cnt += 1
    else:
        for i in range(start, n): #자료의 개수
            res[L] = data[i]
            DFS(L+1, i+1)

DFS(0,0)
print(cnt)

코멘트

조합 활용. 결국 나머지는 중복 순열, 순열과 동일하지만 시작 지점 start를 넘겨줘서 이전 데이터들을 선택 못하게 하는 기능만 추가하면 돼!