수들의 조합
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("input.txt", "r")
def DFS(L, s, sum):
global cnt
if L==m: #3개를 뽑는 경우 m=3
if sum % k ==0: #L은 깊이를 의미함
cnt+=1
else:
for i in range(s, n): #range의 범위는 트리의 가지(자식) 수를 의미한다. i는 branch의 값을 의미한다.
DFS(L+1, i+1, sum+a[i])
if __name__=="__main__":
n, m=map(int, input().split())
a = list(map(int, input().split()))
k = int(input())
cnt=0
DFS(0,0,0)
print(cnt)
Hint
▶s는 start point를 의미한다.
▶sum을 값을 누적하기 위한 조치이다.
▶m은 뽑은 갯수를 의미하는데, 만약에 뽑은 갯수가 3이라면, 깊이(L)은 3이 된다.
▶for i in range(s, n):
# range의 범위는 트리의 가지(자식) 수를 의미한다.
# i는 branch의 값을 의미한다.
추가설명
'파이썬 알고리즘 > 완전탐색과 DFS기초' 카테고리의 다른 글
10.조합구하기 (0) | 2022.11.08 |
---|---|
9. 수열 추측하기 (0) | 2022.11.08 |
8.순열구하기 (0) | 2022.11.08 |
7.동전교환 (0) | 2022.11.07 |
6. 중복순열 구하기(DFS) (0) | 2022.11.07 |