55)수들의 조합

문제

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

 

총 가지수를 출력합니다

 

문제풀이

def go(L, s, tsum):
  global cnt

  if L==K:
    if tsum%M==0:
      cnt+=1
  else:
    for i in range(s, N):
      go(L+1, i+1, tsum+a[i])

N, K=map(int, input().split())
a=list(map(int, input().split()))
M=int(input())
cnt=0
go(0, 0, 0)
print(cnt)

 

import itertools as it

N, K=map(int, input().split())
a=list(map(int, input().split()))
M=int(input())
cnt=0

for x in it.combinations(a, K):
  if sum(x)%M==0:
    cnt+=1

print(cnt)