1182

날짜 : 2023. 03. 01 

사용 언어 : python

 

문제

 

 

코드

import sys
sys.setrecursionlimit(10**5)

n, s = map(int, sys.stdin.readline().split())  # 정수의 개수, 목표값
arr = list(map(int, sys.stdin.readline().split()))  # 숫자 입력
cnt = 0


def back_tracking(cur, sum):  # 현재 인덱스, 더한 수
    #print(cur)
    if cur == n:  # 모든 수 탐색 완료
        if sum == s:  # 총합이 동일하다면
            global cnt
            cnt += 1  # 개수 증가
        return
    else:
        back_tracking(cur + 1, sum)  # 본인 인덱스 값 포함 x
        back_tracking(cur + 1, sum + arr[cur])  # 본인 인덱스 값 포함
    return


back_tracking(0, 0)
if s == 0:
    if cnt == 1: print(0)
    else: print(cnt - 1)
else:
    print(cnt)

 

 

풀이

- 백트래킹을 활용하여 풀이

- cur 변수를 사용하여 현재 위치한 인덱스를 체크하고, cur 인덱스를 포함하여 더한 값이랑 포함하지 않고 더한 값을 구분함으로써 부분수열의 합을 구한다.

- 탐색을 모두 마쳤을 경우(cur의 값이 n에 도달) 더한 값을 비교하여 같다면 전역변수 cnt를 증가시킨다.

- 다만, 공집합까지 포함되었을 수 있기 때문에 조건문을 통해 걸러낸다.

 

 

알게된 점

- 접근은 맞았지만 마지막 s값과 공집합으로 걸러내는 부분에서 꽤 많이 시간을 할애했다.

 

 

참고 사이트

-