isPowerfulBlog

[Solved] BOJ: 1182 | 부분수열의 합 본문

Algorithm

[Solved] BOJ: 1182 | 부분수열의 합

왕밤빵도라에몽 2022. 11. 7. 17:25

문제

길이 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와 같은지 체크한다.

전체 코드

스크린샷, 2022-11-07 17-17-58