Algorithm - 수들의 조합(DFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[수들의 조합(DFS)]

 

N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수가 되는 경우의 수를 출력하는 프로그램을 작성하시오. 예를 들어 5개의 숫자 2, 4, 5, 8, 12가 주어지고 3개를 뽑은 조합의 합이 6의 배수인 조합을 찾으면, {4, 8, 12}와 {2, 4, 12}로 경우의 수는 총 두 가지가 된다.

 

 

*입력 설명

첫 번째 줄에 정수의 개수 N(3 ≤ N ≤ 20)과 임의의 정수 K(2 ≤ K ≤ N)가 주어진다.

두 번째 줄에 N개의 정수가 주어진다.

세 번째 줄에 M이 주어진다.

 

*출력 설명

조건에 맞는 전체 경우의 수를 출력한다.

 

 

---

 

 

풀이(Python)

답안(1)

import sys
sys.stdin = open('AA/input_53.txt', 'rt')

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)
    
# 출력 : 2

 

답안(2) : 라이브러리 활용

import sys
import itertools as it
sys.stdin = open('AA/input_53.txt', 'rt')

n, k = map(int, input().split())
a = list(map(int, input().split()))
m = int(input())
cnt = 0

for x in it.combinations(a, k):
    if sum(x) % m == 0:
        cnt += 1
print(cnt)

# 출력 : 2

 

input_53.txt(입력)

5 3 
2 4 5 8 12
6

 

 

중요내용

1. DFS() 함수의 인자 L은 상태트리의 레벨을 의미한다.
2. DFS() 함수의 인자 s는 조합의 원소를 저장하는 리스트의 인덱스 번호를 의미한다.
3. DFS() 함수의 인자 sum은 조합의 합을 의미한다.
4. 조합은 원소들의 중복을 허용하지 않기 때문에 DFS(L+1, i+1, sum+a[i])에서 인자 s 위치에 ' i+1 '이 들어가는 것이다.
5. itertools 라이브러리의 combinations() 함수는 인자로 들어온 값들을 가지고 만들 수 있는 모든 조합의 결과를 보여준다.
6. combinations(a, k) 코드는 리스트 a에 존재하는 원소들 중 k개를 뽑아서 조합을 만들겠다는 의미이다.
7. 라이브러리를 활용한 답안(2)의 문제접근 방식도 답안(1)의 방식과 동일하다.