Data Structures & Algorithms

[Algorithms] 완전탐색(백트랙킹, 상태트리와 CUT EDGE)/깊이우선탐색(DFS) Basic-수들의 조합(DFS)

숄구-ml 2022. 5. 26. 23:11

 

  • 1. 수가 중복해서 뽑히면 안되고 2. 이미 나온 수의 조합이 순서만 바뀌어서 또 나올 수 없는 상황
  • 그렇다면 이전의 문제인 조합 구하기를 참고하여 응용해서 풀면 되는 것

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def DFS(level, sum, start):
    global cnt
    if level==m:
        if sum % target == 0:
            cnt+=1
    else:
        for i in range(start, n):
            DFS(level+1, sum+arr[i], i+1)
 
 
if __name__=='__main__':
    n, m = map(int, input().split())
    arr = list(map(int, input().split()))
    target = int(input())
 
    cnt=0
    DFS(0, 0, 0)
    print(cnt)
 cs

 

  • python 라이브러리 itertools 를 이용해 매우 간단하게 풀 수도 있다. 그러나 추천하지는 않음.
    • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
        import itertools as it
     
        n, m = map(int, input().split())
        arr = list(map(int, input().split()))
        target = int(input())
     
        cnt = 0
        for x in it.permutations(arr, m):   # 주어진 리스트에서 m개의 조합을 다 불러와라
            if sum(x) % target:
                cnt+=1
        print(cnt)
     
     
    		cs
728x90