programmers.타겟 넘버(swift)

문제 설명

n개의 음이 아닌 정수가 있습니다.

예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 밑의 그림과 같이 다섯개의 방법을 쓸 수 있다.

숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하면 된다.

문제 풀이

import Foundation

var cnt = 0
var targetcopy = 0

func DFS(_ numbers:[Int],_ index:Int,_ sum:Int){

    if index == numbers.count{
        if targetcopy == sum{
            cnt += 1
        }
        return
    }
    DFS(numbers, index + 1, sum + numbers[index])
    DFS(numbers, index + 1, sum - numbers[index])
}

func solution(_ numbers:[Int], _ target:Int) -> Int {

    targetcopy = target
    DFS(numbers, 0, 0)
    return cnt
}

소감

기초 DFS 문제를 푸는 느낌이였다.

DFS를 안다면 누구나 쉽게 풀 수 있는 문제이다.

문제 바로가기