파이썬 알고리즘-52 (DFS/BFS) 수들의 조합

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(v, sum, idx):
    global cnt
    if v == k:
        if sum % m == 0:
            cnt += 1
    else:
        for i in lst[idx:]:
            idx += 1
            dfs(v+1, sum+i, idx)


n, k = map(int, input().split())
lst = list(map(int, input().split()))
m = int(input())

cnt = 0
sum = 0
dfs(0, 0, 0)
print(cnt)

처음에는 함수 안에서 idx+1로 시작점을 증가시키려고 했는데, 막상 실행해 보면 idx = 2가 반복해서 나왔다. 원래 의도는 idx가 계속 증가하면서 시작점이 커지므로 반복문이 도는 횟수도 적어져야 하는데, 함수는 재귀적으로 2번까지밖에 실행되지 않으므로 idx = 2에서 멈춘 것이다. 이를 해결하기 위해 반복문이 시작될 때 idx에 +1을 해 줌으로써 시작점이 계속 증가할 수 있도록 하였다.

풀이

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)

반성점

배운 것

• 어제 배운 것에서 조합은 반복문의 시작점이 다음 레벨에서는 +1부터 시작한다고 했는데 그 점을 제대로 이해하지 못하고 있었다. 인자인 시작점(s)을 놓고, 반복문은 s부터 돌면서 다음 함수를 불러올 때, 다음 함수의 인자 s에 i+1을 넣어서 다음 함수의 반복문에서는 i+1이 시작점이 되도록 한다.