[BaekJoon] 1182번 : 부분수열의 합 (Python)

코딩 1일 1문제! 오늘의 문제는 백준의 부분수열의 합 입니다.

1182번: 부분수열의 합

👨🏻‍💻 문제 풀이

숫자 리스트가 주어지면 해당 리스트의 부분수열의 합이 입력받은 숫자 S와 같아질 경우 카운팅하여 

조건을 만족하는 부분수열의 개수가 몇 개인지 구하는 문제입니다.

from itertools import combinations

부분 수열을 구하는데에는 itertools의 combinations를 활용했습니다.

N, S = map(int, input().split())
numbers = list(map(int, input().split()))

예제 입력을 받기위한 부분을 작성합니다.

answer = 0
    
for comb_num in range(1, len(numbers) + 1):
    comb_S = [comb for comb in combinations(numbers, comb_num) if sum(comb) == S]
    answer += len(comb_S)

1부터 입력받은 숫자 목록의 길이 까지 반복문을 돌면서

combination로 부분수열을 만들어주고 이 부분수열의 합이 S와 같은 경우에만 남겨둡니다.

각 길이에 따라 남은 부분수열의 개수를 더해주면 됩니다.

 

전체 코드는 아래를 참고해주세요.

👨🏻‍💻 코드 ( Solution )

from itertools import combinations

def subsequence_sum(numbers, S):
    answer = 0
    
    for comb_num in range(1, len(numbers) + 1):
        comb_S = [comb for comb in combinations(numbers, comb_num) if sum(comb) == S]
        answer += len(comb_S)
        
    return answer

if __name__ == "__main__":
    N, S = map(int, input().split())
    numbers = list(map(int, input().split()))
        
    print(subsequence_sum(numbers, S))

GitHub - SOMJANG/CODINGTEST_PRACTICE: 1일 1문제 since 2020.02.07