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
반응형
'TIL - 프로그래밍 > Python 알고리즘' 카테고리의 다른 글
[프로그래머스] Lv.1 소수 만들기 - Python (0) | 2022.06.09 |
---|---|
[백준] 1018. 체스판 다시 칠하기 - Python (0) | 2022.06.07 |
[백준] 1987. 알파벳 - Python (0) | 2022.06.06 |
[프로그래머스] Lv.2 오픈채팅방 - Python (0) | 2022.06.05 |
[프로그래머스] Lv.1 숫자 문자열과 영단어 - Python (0) | 2022.06.04 |
댓글