파이썬 알고리즘 문제풀이 입문] 완전탐색 (백트랙킹, 상태트리와 CUT EDGE) / DFS(깊이우선탐색) 기초 - 수들의 조합 (DFS)

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수는 몇 개가 있는지 출력하는 프로그램을 작성하세요.

 

 

 

풀이

• 내 풀이

import sys
input = sys.stdin.readline

def DFS(index, start):
    global cnt

    if index == K:
        if sum(res)%M == 0:
            cnt += 1
    else:
        for i in range(start, len(numbers)):
            res[index] = numbers[i]
            DFS(index+1, i+1)

N, K = map(int, input().split())
numbers = list(map(int, input().split()))
M = int(input())

cnt = 0
res = [0] * K
DFS(0, 0)
print(cnt)

• 답안 : Python

import sys
input = sys.stdin.readline

def DFS(index, start, sum):
    global cnt

    if index == K:
        if sum%M == 0:
            cnt += 1
    else:
        for i in range(start, N):
            DFS(index+1, i+1, sum+numbers[i])

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

- 이전 문제인 '조합 구하기' 풀이 방법과 거의 유사하나, 다른 점은 1부터 N까지의 숫자들을 가지고 조합을 구하는 것이 아니라 입력받은 리스트의 값들 중에서 조합을 구하는 것이다.

- 때문에 넘겨받는 start는 numbers의 시작 인덱스가 된다.

- 답안과 내 풀와 다른 점은,

   → 나 : res 리스트를 사용하여 뽑은 값들을 저장한 뒤, sum()으로 res 리스트에 담긴 값들의 합을 구하여 M의 배수인지 판단한다.

   → 답안 : 애초에 DFS로 값을 넘길 때 sum도 같이 넘겨주되, sum에 numbers[i]를 더해준 누적 합을 넘겨준다.

   (굳이 리스트를 따로 사용할 필요가 없다는 것을 알게 되었다.)

 

 

cf.) 라이브러리를 사용한 답안

import sys
from itertools import combinations
input = sys.stdin.readline

N, K = map(int, input().split())
numbers = list(map(int, input().split()))
M = int(input())
count = 0

for element in combinations(numbers, K):
    if sum(element) % M == 0:
        count += 1

print(count)