파이썬 알고리즘 052 | 수들의 조합

52. 수들의 조합

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

<내 풀이>

def DFS(x,s):
    global cnt
    if x==k:
        if sum(res)%m==0:
            cnt+=1
        return    
    else :
        for i in range(s,n):
            res[x]=a[i]
            DFS(x+1,i+1)

if __name__=='__main__' :
    n, k = map(int, input().split())
    a=list(map(int, input().split()))
    m=int(input())
    res=[0]*(k)
    cnt=0
    DFS(0,0)
    print(cnt)
    

<풀이>

import sys
sys.stdin=open("input.txt", "r")
def DFS(L, s, sum):
    global cnt
    if L==k:
        if sum%m==0:
            cnt+=1
    else:
        for i in range(s, n):
            DFS(L+1, i+1, sum+a[i])
 
if __name__=="__main__":
    n, k=map(int, input().split())
    a=list(map(int, input().split()))
    m=int(input())
    cnt=0
    DFS(0, 0, 0)
    print(cnt)
    

+++ 라이브러리를 이용한 조합

import itertools as it #순열이랑 조합을 바로 구해주는 함수
n,k = map(int, input().split())
a=list(map(int, inpur().split()))
m=int(input())
cnt=0
for x in it.combinations(a,k) : 
    print(x)
    

=>이렇게 하면 a를 k개 뽑아서 만들 수 있는 조합의 경우 잘 출력이 된다

import itertools as it #순열이랑 조합을 바로 구해주는 함수
n,k = map(int, input().split())
a=list(map(int, inpur().split()))
m=int(input())
cnt=0
for x in it.combinations(a,k) : 
    if sum(x)%m==0:
        cnt+=1
print(cnt)

<반성점>

• 지금까지 배운 DFS를 이용한 조합, 순열, 중복순열, 부분집합, 다 유형별로 익히고 복습하기

<배운 점>

• s 갱신시킬 때 i+1 로 하는 것이다
  else :
  for i in range(s,n):
  res[x]=a[i]
  DFS(x+1,i+1)
• 몫이 // 고 나머지는 %다

<2회독 내 풀이>

def DFS(x,s) : 
    global cnt
    if x==k : 
        if sum(res)%m==0:
            cnt+=1
        return
    else :
        for i in range(s,n) : #범위 설정 잘 고려해가며 하기
            res[x]=a[i]
            DFS(x+1, i+1)
if __name__=='__main__' :
    n, k = map(int, input().split())
    a=list(map(int, input().split()))
    m= int(input())
    res=[0]*(k)
    cnt=0
    DFS(0,0)
    print(cnt)