(Python/🥈2)백준 알고리즘 1182번:부분수열의 합

 

문제 바로가기 

백준 알고리즘 부분수열의 합

문제:

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

입력:

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

 

출력:

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

 

풀이:

1.

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N, S = map(int,sys.stdin.readline().rstrip().split(" "))
arr = list(map(int,sys.stdin.readline().rstrip().split(" ")))
cnt = 0
res = []
def solution(idx):
    global cnt
    if sum(res) == S and len(res) > 0:
        cnt += 1

    for i in range(idx,N):
        res.append(arr[i])
        solution(i+1)
        res.pop()

solution(0)
print(cnt)

그 전에 N과M때 하던 방식

 

 

2. 

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N, S = map(int,sys.stdin.readline().rstrip().split(" "))
arr = list(map(int,sys.stdin.readline().rstrip().split(" ")))
cnt = 0

def solution(num, sum):
    global cnt
    if num >= N:  # 수열의 끝까지 도달하면 종료
        return
    sum += arr[num]  # 현재 원소를 더함
    if sum == S:  # 원소의 합이 S와 같다면 경우의 수 증가
        cnt += 1

    solution(num + 1, sum)  # 다음 원소를 더하는 경우
    solution(num + 1, sum - arr[num])  # 다음 원소를 더하지 않는 경우

solution(0, 0)  # 재귀 함수 호출, 초기값은 0으로 설정
print(cnt)  # 결과 출력

 

요즘 내가 쓰는 방식

solution에 2개가 있는건

다음 숫자를 선택했을때.

다음 숫자를 선택하지 않았을때를 나눠서 하는것이다.

 

result = []
def solution(num, total):
    global cnt,res,result
    if num == N:
        if total == S and len(result)>0:
            cnt += 1
        return
    result.append(arr[num])
    res += arr[num]
    solution(num+1, res)
    res -= arr[num]
    result.pop()
    solution(num+1, res)
solution(0, 0)
print(cnt)

 

또 이런 방법도 있다.

이건 저번에 치킨배달 문제를 쓸때 푼 방법인데. 조합의 수를 재귀로 나타내는것이다.

굳이 몰라도 될거같다.