swift ) 백준 1010 다리놓기

 

마찬가지로 조합 문제

파스칼의삼각형을 재귀함수로 만듬

 

// 1010 다리놓기, 파스칼의 삼각형 이용

let caseNum = Int(readLine()!)!
var resultArr = Array(repeating: Array(repeating: 0, count: 31), count: 31)

for _ in 1...caseNum {
	let input = readLine()!.split(separator: " ").map{Int(String($0))!}
	print(getCombination(input[1], input[0]))
}

func getCombination (_ a:Int, _ b:Int) -> Int {
	
	if a == b || b == 0 {
		return 1
	}
	if resultArr[a][b] != 0 { // 이 부분이 중요, 없으면 시간초과 : 이미 탐색했던 경우는 바로 반환함.
		return resultArr[a][b]
	}
	
	resultArr[a][b] = getCombination(a-1, b-1) + getCombination(a-1, b)
	return resultArr[a][b]
}