[Swift] 알고리즘 공부 - 타겟 넘

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

입출력 예

numbers                target                    return

[1,1,1,1,1]	3	5
[4,1,2,1]	4	2

 

설명

1. index는 numbers의 index값, sum은 총 합이다.

2. 만약 index를 다돌았을경우 sum의 값이 target의 값과 맞는지 비교하고 맞으면 count 값을 +1 해준다.

3. 이걸 재귀적으로 계속돌린다.

 

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    
    var count = 0

    dfs(index: 0, sum: 0)
    
    return count
}

func dfs(index: Int, sum: Int) {
    if index == numbers.count {
        if sum == target { count += 1 }
        	return
    }
        
    dfs(index: index+1, sum: sum + numbers[index])
    dfs(index: index+1, sum: sum - numbers[index])
}

 

위에 글은 예를 들어 number = [1,2,3,4,5]이고 target이 5일때 dfs가 도는 경우다.

dfs(0, 0)
|__dfs(1, 1)
|  |__dfs(2, 3)
|  |  |__dfs(3, 6)
|  |  |  |__dfs(4, 10)
|  |  |  |  |__dfs(5, 15) -> sum == target, count = 1
|  |  |  |__dfs(4, 2)
|  |  |__dfs(3, 4)
|  |  |  |__dfs(4, 8)
|  |  |  |__dfs(4, 0) -> sum == target, count = 2
|  |__dfs(2, -1)
|  |  |__dfs(3, 2)
|  |  |  |__dfs(4, 6)
|  |  |  |__dfs(4, 0) -> sum == target, count = 3
|  |__dfs(3, 0)
|  |__dfs(3, -2)
|__dfs(1, -1)
   |__dfs(2, 1)
   |  |__dfs(3, 4)
   |  |  |__dfs(4, 8)
   |  |  |__dfs(4, 0) -> sum == target, count = 4
   |__dfs(3, -2)
   |  |__dfs(4, 2)
   |  |__dfs(4, -2)

dfs문제는 제귀를 이용해서 풀어야하는데 아직 익숙하지 않은것 같다