[Python-CodingTest] 6-11. 수들의 조합 (DFS: 깊이우선탐색)

수들의 조합

문제 정리

입력

5 3
2 4 5 8 12
6

처리 과정

1. 이전에 풀었던 조합 문제와 유사하지만,
   여기에서는 1,2,3,4,5 같은 1부터 n까지 수가 아니라 2,4,5,8,12 같이 요소가 n개인 무작위 리스트(=lst)가 주어진다.
2. 조합의 합이 m의 배수인지 확인하기 위해서 DFS의 인자로 sum을 준다.
3. 이전 조합 풀이와 마찬가지로 for문의 시작은 src
4. sum에는 lst[i]의 값을 누적한다.

출력

2

풀이

import sys
sys.stdin = open("./input/in11.txt", "rt")

def DFS(L,src,sum):
    global cnt
    if L==k:
        # for x in res:
        #     print(x,end=' ')
        # print()
        if sum%m==0: # m의 배수라면 cnt+=1
            cnt+=1
    else:
        for i in range(src,n): # 이번에는 n+1이 아니라 n! (이전에는 인덱스 번호와 일치시키려고 n+1까지 한거였음..)
            # res[L]=lst[i] # res를 출력해보고 싶다면 이런식으로!
            DFS(L+1,i+1,sum+lst[i])


if __name__=="__main__":
    n,k=map(int,input().split())
    lst=list(map(int,input().split()))
    m=int(input())

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

정리

• 문제에서는 조합의 경우들을 출력할 필요는 없었지만,
  출력하고 싶다면 이전 조합 풀이에서처럼 res[L]=i가 아니라 res[L]=lst[i]를 할 것!

---

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

맨 위로 이동하기