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

2024년 7월 12일

문제 링크 : 백준 1182번 - 부분수열의 합

문제

 

 

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

 

알고리즘 분류

• 백트래킹
• 브루트포스 알고리즘

---

 

문제 접근

 

백트래킹을 활용해 완전탐색 해야하는 문제이다.

 

길이가 1일 때의 부분 수열부터 길이가 N일 때의 부분수열까지 모든 조합을 구해 합이 0이 되는 케이스가 총 몇 개인지 구하는 문제이다.

 

N이 최대 20이기 때문에 2초의 시간 제한도 거뜬하리라 판단하였다.

 

---

입력 예제

 

5 0
-7 -3 -2 5 8

 

 

 

출력 예제

 

1

 

 

---

전체 코드

 

# 1182

def backTracking(nowLen, maxLen, nowNums, nowIdx):
    global result
    if maxLen == nowLen:
        if sum(nowNums) == S:
            result += 1
        return
    for i in range(nowIdx, N):
        nowNums.append(nums[i])
        backTracking(nowLen + 1, maxLen, nowNums, i + 1)
        nowNums.pop()

if __name__ == "__main__":
    N, S = map(int ,input().split())

    nums = list(map(int, input().split()))
    result = 0

    for maxLen in range(1, N + 1):
        backTracking(0, maxLen, [], 0)

    print(result)

 

 

---

풀이 후기

 

완전 탐색을 활용할 수 있는 문제는 보통 입력값에서 힌트를 얻을 수 있다.

N이 현저히 작은 수라면 완전 탐색, 필요에 의하면 백트래킹으로 접근할 수 있어야 한다.