[DFS] 동전교환

시간초과 답안

import Foundation

var res = Int.max
var n = 3
var a = [1, 2, 5]
a.sort(by: >)

var m = 15

func DFS(_ L: Int, _ sum: Int) {

	if sum > m {
        return
    }
    if sum == m {
        res = min(res, L)
        return
    }
    for i in 0..<n {
        DFS(L + 1, sum + a[i])
    }
}

DFS(0, 0)
print(res)

시간 줄이기

import Foundation

var res = Int.max
var n = 3
var a = [1, 2, 5]
a.sort(by: >)

var m = 15

func DFS(_ L: Int, _ sum: Int) {
	
    //res 넘기면 종료
	if L> res { 
    	return
    }

    if sum > m {
        return
    }
    
    if sum == m {
        res = min(res, L)
        return
    }
    
    for i in 0..<n {
        DFS(L + 1, sum + a[i])
    }
}

DFS(0, 0)
print(res)

트리