[BOJ] 부분수열의 합(1182) - PYTHON

수열의 길이 N, 정수 S와 길이와 수열이 입력으로 들어올 때 부분 수열의 합이 S가 나오는 경우의 수를 구하는 문제다.
(단, 1 <=N <=20, -1,000,000 <=S <=1,000,000) 

시간 복잡도: O(2^20)

1182번: 부분수열의 합

---

풀이 과정

부분수열의 합이 S가 되는 지를 검사하려면 모든 부분 수열을 구해서 합이 S가 되는지 검사해야 한다. 즉 모든 경우를 탐색하는 완전 탐색을 활용해 답을 구한다. 수열의 모든 원소에 대해 값이 들어가거나 안 들어가는 2가지 경우가 있으므로, 모든 경우를 검사하는 데는 2^20이 나온다. 이때 20은 수열의 최대 길이다.

부분 수열의 합을 구할 때는 배열을 하나 더 선언한 다음에 현재 있는 배열의 원소들에 현재 값을 더한 값들을 추가하고, 마지막으로 현재 값을 추가하는 방식으로 구한다. 

---

코드

N, target = map(int,input().split())
arr = list(map(int, input().split()))
numArr = []
for i in arr:
    for k in range(len(numArr)):
        numArr.append(i + numArr[k])
    numArr.append(i)
print(numArr.count(target))

 

주석 추가

N, target = map(int, input().split())  # 수열의 길이, 찾는 값
arr = list(map(int, input().split()))  # 수열 입력
numArr = []  # 부분수열의 합 들을 저장할 배열
for i in arr:  # 수열의 각 원소
    for k in range(len(numArr)):  # 현재 저장한 배열값에서
        numArr.append(i + numArr[k])  # 현재 값을 저장한 값을 추가
    numArr.append(i)  # 마지막에 현재 값 추가
print(numArr.count(target))  # 찾는 값의 개수 출력

---

채점결과