1. 문제 설명

양궁대회

2. 문제 분석

DFS를 통해 현재 쏠 수 있는 화살의 수를 카운트, 마지막 과녁까지 쐈을 때 라이언이 이겼고 로컬 최댓값보다 현재 점수 차가 클 때에만 라이언의 화살 정보를 업데이트했다. 이 경우 마지막에 차가 0이라면 비긴 것이므로 [-1]을 리턴하는 것에 주의하자.

3. 나의 풀이

import Foundation

func solution(_ n:Int, _ info:[Int]) -> [Int] {
    let info = Array(info.reversed())
    var scoreDiff = 0
    var lionArrows = [-1]
    
    func depthFirstSearch(_ curLionArrowCount: Int, _ curLionArrows: [Int], _ curArrowIndex: Int, _ curLionScore: Int, _ curApeachScore: Int) {
        if curArrowIndex == info.count {
            let curDiff = curLionScore - curApeachScore
            if curLionArrowCount == 0 && scoreDiff <= curDiff {
                scoreDiff = curDiff
                lionArrows = curLionArrows
            }
            return
        }
        
        for arrow in 0...curLionArrowCount {
            let nextScores: (Int, Int)
            if info[curArrowIndex] == 0 && arrow == 0 {
                nextScores = (0, 0)
            } else if info[curArrowIndex] >= arrow {
                nextScores = (0, curArrowIndex)
            } else {
                nextScores = (curArrowIndex, 0)
            }
            let nextLionScore = curLionScore + nextScores.0
            let nextApeachScore = curApeachScore + nextScores.1
            depthFirstSearch(curLionArrowCount - arrow, curLionArrows + [arrow], curArrowIndex + 1, nextLionScore, nextApeachScore)
        }
    }
    depthFirstSearch(n, [], 0, 0, 0)
    let answers = scoreDiff == 0 ? [-1] : Array(lionArrows.reversed())
    return answers
}