[파이썬/Python] 백준 1182번: 부분수열의 합

숨·2024년 8월 6일

코테

알고리즘 문제 풀이

목록 보기

42/105

📌 문제 : 백준 1182번

📌 문제 탐색하기

N : 정수의 개수 ( $1 ≤ N ≤ 20$ )
S : 정수 ( $|S| ≤ 1,000,000$ )

✅ 입력 조건
1. 첫번째 줄 N, S 입력
2. N개의 정수 입력
✅ 출력 조건
1. 합이 S가 되는 부분수열의 개수 출력

입력받은 N개의 정수를 담은 리스트로 만들 수 있는 모든 조합들을 구하고,
그 합들을 계산해 저장한다.
저장한 합들 중에 S와 동일한 경우의 수를 세서 출력하면 될 것이다.

모든 조합을 구하기 위해 itertools 라이브러리의 combinations를 호출한다.

📖 combinations(arr, r) 함수

첫번째 매개변수 arr : 조합 구하고자 하는 배열 의미

두번째 매개변수 r: 몇 개의 요소를 가지는 조합을 구할지 의미

요소의 수 상관 없이 모든 조합을 계산할 것이므로,
for문을 통해 1개부터 N개까지의 요소 수를 가지는 조합을 계산한다.
만들어진 조합의 합을 계산해서 S와 동일하면 count해준다.

가능한 시간복잡도

모든 조합을 찾아 합을 계산하는 이중 for문 → $O(N * 2^N) = O(N * 2^N)$

최종 시간복잡도
최악의 경우 $O(20 * 2^{20})$ 이다. 이는 약 2백만 번의 연산이 필요하므로 2초 내에 연산이 가능하다.

알고리즘 선택

완전탐색으로 모든 조합을 계산해 합을 구하여 S와 동일한 값이 있을 경우를 세는 방법

📌 코드 설계하기

N, S 입력
N개의 정수 입력받아 리스트 저장
합이 S인 부분 수열의 개수 저장하는 변수 정의
정수들로 만들 수 있는 모든 조합 확인

📌 시도 회차 수정 사항

1회차

📌 정답 코드

import sys
from itertools import combinations

input = sys.stdin.readline

# N, S 입력
N, S = map(int, input().split())

# N개의 정수 입력받아 리스트 저장
nums = list(map(int, input().split()))

# 합이 S인 부분 수열의 개수 저장하는 변수 정의
count = 0

# 정수들로 만들 수 있는 모든 조합 확인
for i in range(1, N+1):
    for j in combinations(nums, i):
        if sum(j) == S:
            count += 1

# 결과 출력
print(count)