문제
수들의 조합
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(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)
-DFS(L, s, sum)
L:level 층위
s:start 시작점 -->리스트 a의 순서를 기준으로! (원소 기준 아님) 0,1,2...
sum: 합계
경로 탐색(그래프 DFS : Depth First Search) python (0) | 2021.08.26 |
---|---|
인접 행렬 python (0) | 2021.08.26 |
조합 구하기 (0) | 2021.08.25 |
수열 추측하기 (0) | 2021.08.25 |
순열 구하기 (0) | 2021.08.25 |
댓글 영역