isPowerfulBlog
[Solved] BOJ: 1182 | 부분수열의 합 본문
문제
길이 N짜리 수열을 입력받아
이 수열의 부분수열의 합이 S가 되도록하는 부분수열의 개수를 구해보자
입력과 출력
입력
첫째줄에 수열의 길이 N과 부분수열의 합이 되어야하는 값 S를 입력받는다.
둘째줄에 수열을 입력받는다.
출력
합이 S가 되도록하는 부분수열의 개수를 출력한다.
문제 해결 요약
i개의 수열 조합에 대한 sum을 구해 -> 브루트포스
s와 같은지 확인
코드 설명
import 및 입력받기
수열 정보를 입력받는다.
-
from itertools import combinations
import sys
input = sys.stdin.readline
n, s = map(int, input().split())
num = list(map(int, input().split()))
부분수열의 합
부분수열의 합이 S인지 체크한다.
-
cnt = 0
for i in range(1, n+1):
for combi in combinations(num, i):
if sum(combi) == s:
cnt += 1
- 길이가 1부터 n까지인 부분 수열들을 각각 구하여
- sum 값이 S와 같은지 체크한다.
전체 코드
'Algorithm' 카테고리의 다른 글
[Solved] BOJ: 1759 | 암호 만들기 (0) | 2022.11.11 |
---|---|
[Solved] BOJ: 14889 | 스타트와 링크 (0) | 2022.11.11 |
[Solved] BOJ: 11651 | 좌표 정렬하기 2 (0) | 2022.11.11 |
[Solved] BOJ: 15686 | 치킨거리 (0) | 2022.11.07 |
[Solved] BOJ: 2468 | 안전영역 (0) | 2022.11.07 |