2817. 부분 수열의 합 (D3 python)

📌  문제 바로가기

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

💡접근 방법

• 값을 포함하는 경우, 포함하지 않는 경우 -> 2가지의 경우의 수로 갈래가 나뉘고,
  • 그 갈래 중에 K값과 같은 갯수를 구하기

• 여러 갈래로 뻗어나간다 -> dfs로 접근 해보자!
  • 포함하는 경우, 포함하지 않는 경우 -> dfs 재귀함수를 2번 호출해서 하나는 포함O, 하나는 포함X

• sum을 전달하면서 sum==K이면 
  • count +=1 하고, return

 

 

🤔  return 을 안하면?

return을 안 하면 그 갈래가 끝나지 않고 중복 계산이 된다

 

예를 들어 data = [1,2,1,2] 이고 K=3일때

 

1,2,1,2

OO       : 1번째 인덱스 더하고 난 후 count ++

OOX     : 2번째 인덱스 안 더하고 난 후 count++

OOXX   : 3번째 인덱스 안 더하고 난 후 count++

OXXO   : 3번째 인덱스 더하고 난 후 count++

 

XOO     :  2번째 인덱스 더하고 난 후 count++

XOOX   :  3번째 인덱스 안 더하고 난 후 count++

XXOO   :  3번째 인덱스 더하고 난 후 count++

 

return값을 넣지 않으면 그 이후에도 계속 count++가 되어서 중복이 되어 7이 나온다

 

 

✅  return을 넣으면

1,2,1,2

OO|       : 1번째 인덱스 더하고 난 후 count ++ return

OOX     : 2번째 인덱스 안 더하고 난 후 count++

OOXX   : 3번째 인덱스 안 더하고 난 후 count++

OXXO|   : 3번째 인덱스 더하고 난 후 count++ return

 

XOO|     :  2번째 인덱스 더하고 난 후 count++ return

XOOX   :  3번째 인덱스 안 더하고 난 후 count++

XXOO|   :  3번째 인덱스 더하고 난 후 count++ return

 

중복을 제거하여 4가 나온다.

 

 

💡 풀이코드

def dfs(index, sum = 0):
    global count

    if sum == K:
        count +=1
        return  #return 을 하면 그 이후 data[index] 안 더하고 이 갈래는 끝남

    if index == N:
        return

    dfs(index+1, sum + data[index]) #포함한 경우
    dfs(index+1, sum) #포함하지 않은 경우

tc = int(input())

for i in range(tc):
    N, K = map(int, input().split())
    count = 0
    data = list(map(int,input().split()))
    dfs(0)
    print('#{} {}'.format(i+1, count))