[김태원 알고리즘] 수들의 조합 (DFS)

사용 언어: Python3

문제

풀이

내 풀이

def DFS(L, S):
    global cnt
    if L == K:
        if sum(res) % M == 0: # 조합의 합이 M의 배수인지 검증
            cnt += 1
    else:
        for i in range(S, N):
            res[L] = lst[i]
            DFS(L+1, i+1)

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

cnt = 0
res = [0] * K # 완성된 조합을 저장할 리스트

DFS(0, 0)
print(cnt)

• 정답!
  • 복잡한 예제도 통과하였다.

다른 풀이

def DFS(L, S, pSum): # S는 시작 인덱스, pSum은 누적합
    global cnt
    if L == K and pSum % M == 0:
        cnt += 1
    else:
        for i in range(S, N):
            DFS(L+1, i+1, pSum+lst[i]) # pSum에 선택된 원소 누적

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

cnt = 0

DFS(0, 0, 0)
print(cnt)

• res 변수에 완성된 조합을 따로 저장하지 않고, DFS()의 파라미터로 pSum을 전달해 선택된 원소를 누적하는 방법이다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기