수들의 조합

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

예를 들면 5개의 숫자 2 4 5 8 12가 주어지고,

3개를 뽑은 조합의 합이 6의 배수인 조합을 찾으면 4+8+12 2+4+12로 2가지가 있습니다.

 

▣ 입력설명

첫줄에 정수의 개수 N(3<=N<=20)과 임의의 정수 K(2<=K<=N)가 주어지고,

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

세 번째 줄에 M이 주어집니다.

 

▣ 출력설명

총 가지수를 출력합니다.

 

▣ 입력예제

5 3

2 4 5 8 12

6

 

▣ 출력예제

2

---

내가 쓴 코드

def DFS(v, idx, cur_sum):
    global cnt

    if v == K and cur_sum % M == 0:
        cnt += 1
    elif v < K:
        for i in range(idx, N):
            result[v] = nums[i]
            DFS(v+1, i+1, cur_sum+nums[i])


if __name__=="__main__":
    N, K = map(int,input().split())
    nums = list(map(int, input().split()))
    M = int(input())

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

 

모범답안

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)

 

느낀점

1. 일단 모범답안이랑 흐름이 완저니 똑같다. 아주 잘함

2. 단, 문제점이 크게 두개 있는데
일단 DFS깊이가 K가 됐을때 먼저 조건 안으로 들어오게 해서
더 깊은 레벨로 안들어가게 하면 elif를 안쓰고 그냥 else로 해도 되었을 것

3. 그리고 result 리스트는 필요없었다. 조합을 이루는 숫자는 관심없고
합만 중요하니까!! 반사적으로 만드는건 바보같은 짓

4. 그래도 넘 잘했다! 리뷰하고 다시 써보장~

 

---

 

다시 풀어보기

#다시
def DFS(v, start_idx, cur_sum):
    global cnt
    if v == K:
        if cur_sum % M == 0:
            cnt += 1
    else:
        for i in range(start_idx,N):
            DFS(v+1, i+1, cur_sum+nums[i])

if __name__ == "__main__":
    N, K = map(int, input().split())
    nums = list(map(int, input().split()))
    M = int(input())

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

 

---

라이브러리로 풀어보기: 참고만!!

'''
라이브러리에 의존하면 안됨!
기본은 재귀함수로 순열과 조합을 구현하는 것..
라이브러리는 참고용!

1. 조합 구하기
import itertools as it
a = [1,2,3,4,5]
k = 3

for x in it.combinations(a,k):
= 5C3
조합 하나하나씩 x에 튜플 형태로 담김
'''

import sys
sys.stdin = open("input.txt",'rt')
import itertools as it

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)