본문 바로가기
TIL - 프로그래밍/Python 알고리즘

[백준] 1182. 부분수열의 합 - Python

by chaemj97 2022. 6. 6.
728x90

https://www.acmicpc.net/problem/1182

 

1182번: 부분수열의 합

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net


  • 코드
from itertools import combinations

# N개의 정수로 이루어진 수열, 부분수열 중 수열의 원소 합이 S 되는 경우의 수 구하기
N,S = map(int,input().split())
sequence = list(map(int,input().split()))

cnt = 0
# 조합으로 풀기
# 부분집합의 원소의 개수가 i인 부분집합의 집합 구하기
for i in range(1,len(sequence)+1):
    comb = list(combinations(sequence,i))
    # 각 부분집합의 합이 S인가 확인
    for com in comb:
        if sum(list(com)) == S:
            cnt += 1

print(cnt)

  • 풀면서 배운 점
    • 조합
      • from itertools import combinations
728x90
반응형

댓글