백준 1192 부분수열의 합 문제풀이

문제 

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

 

문제 접근 방식

이전 문제와 유사하나 수열의 크기가 고정되어 있지 않다는 것이 조금 다르다.

조합을 이용해서 풀 수 있고 재귀함수를 사용해서 풀 수도 있다. 재귀함수 연습을 위해 후자의 방식으로 문제를 풀었다.

 

 

시간 복잡도

최대 정수 개수에 대한 경우의 수는 20C1+20C2+20C3 + ...+ 20C20 를 계산한 값이며, 이는 파스칼의 삼각형 공식을 활용하면 2^20이며 이는 2^10 => 10^3 으로 치환을 하면 10^6 이된다. 대략 경우의 수는 10^6가지이며, 모두 순회해도 시간 효율성에서 걸릴 일은 없다.

 

 

코드

# dfs = 현재 카드 순서인 index까지 합이 total일 때, s와 같은 경우의 수가 몇개인지 반환해주는 함수
def dfs(index,total):

    # 현재 위치에서 count=0 으로 설정하고, 지금가지의 합(total)이 s와 같다면 count 를 1 증가시킨다.
    # 지금까지의 합이 s와 같아도 계속해서 수를 뽑아도 된다는 점이 이전 재귀함수와는 다르다.(탈출 조건이 없다)
    count=0
    if total==s:
        count+=1

    # 이후 숫자에 대해서 total을 계산해서 다시 dfs를 호출해준다.
    for i in range(index+1,n):
        count+=dfs(i,total+li[i])

    return count



if __name__=='__main__':
    global n,s,li
    n,s=map(int,input().split())
    li=list(map(int,input().split()))
    answer=dfs(-1,0)
    
    # 구현한 함수 dfs에서 s는 0일 경우 의미 없는 경우의 수가 1이 세지게 되므로 예외적으로 1을 빼준다.
    if s==0:
        answer-=1
    print(answer)

 

 

 

회고

지금까지 구한 합이 s와 같으면 거기서 return 하는 것이 아니라 계속해서 다음 숫자를 뽑아줘야하는 것이 이전 재귀함수 문제와는 다르다. 

또한, 구현한 dfs 같은 경우 s에 0 이 입력되는 경우 의미없는 경우의 수 1개가 추가되는 예외 상황이 발생하므로 이것을 처리해주는 것도 잊지 말아야한다.