2817. 부분 수열의 합

본 글의 내용은 절대적으로 좋은 코드라는 보장이 없습니다. 글을 읽어보시다가 "이 사람은 이런 식으로 짰구나. 되게 허접하게 짰네?" 라는 생각이 드시면 댓글을 통해서 좋은 가르침과 의견을 주시면 감사합니다!!

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7IzvG6EksDFAXB&categoryId=AV7IzvG6EksDFAXB&categoryType=CODE&&&

SW Expert Academy

기본 아이디어

• 부분집합의 조합으로 나올 수 있는 합의 경우의 수를 구하고 그 합이 원하는 합과 동일할 경우 count를 늘려주는 방식

 

import sys
sys.stdin = open('input.txt', 'r')

T = int(input())

for tc in range(T):
    N, K = map(int, input().split())
    nums = list(map(int, input().split()))

    allSum = sum(nums)

    sums = []
    count = 0
    for num in nums:
        lenSums = len(sums)
        sums.append(num)
        if num == K:
            count += 1
        for s in range(lenSums):
            newSum = sums[s] + num
            if newSum < K:
                sums.append(newSum)
            elif newSum == K:
                count += 1

    print('#{} {}'.format(tc+1, count))