[SWEA 2817] 부분 수열의 합

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7IzvG6EksDFAXB&categoryId=AV7IzvG6EksDFAXB&categoryType=CODE&problemTitle=%EB%B6%80%EB%B6%84&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

 

🔥 작성 코드 (🌪️61,672kb 3,888ms)

# 부분 수열의 합

T = int(input())
for test_case in range(1, T+1):
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    result = 0
    for i in range(1<<len(A)):
        tot = 0
        for j in range(len(A)):
            if i & (1<<j):
                tot += A[j]
        if tot == K:
            result += 1

    print(f'#{test_case} {result}')

 

⭕ 해설

1. 비트 연산자를 이용하여 입력받은 리스트 A에 대한 부분 집합을 모두 확인합니다.
   • 만약 A = [1, 2, 3, 4] 라면 for j에서 [], [1], [2], [1, 2], [3], [1, 3] [2, 3], [1, 2, 3] ,... [1, 2, 3, 4] 까지 확인
   • i의 범위가 1<<len(A)인 것은 len(A) ** 2 만큼(부분 집합의 총 개수) 확인하기 위함.
   • j의 범위는 i의 값이 len(A)만큼 0과 1로 이루어져 있기 때문
     •  0000 0001 0010 0011 ... 1110 1111 까지 총 16가지
     •  위의 값과 비교하는 j는 1<<j 를 통해 0001 0010 0100 1000으로 입력됩니다.
2.  i & (1<<j) 를 이용하여 i가 의미하는 부분집합의 원소들을 확인하고 그것을 tot에 더해줍니다.
3.  부분집합의 합이 K 이면 result에 1을 더해줍니다.
4.  입력받은 수열 A의 부분집합 중 합이 K 인 값을 반환합니다.