[Algorithm] 양궁 대회

[hwangJi-dev]

💬 Idea

라이언이 가장 높은 점수차로 어피치를 이길 수 있는 경우를 찾는 DFS 문제이다.

1. 라이언의 점수판을 만든다. (0점부터 10점까지를 기록할 수 있도록)
2. dfs를 수행할 재귀함수를 설계한다.
   • [ dfs 재귀함수 설계 조건 ]

     1. ⭐️ return 지점 찾기 → 남은 화살이 0개 이하이거나, 최종 index가 10에 도달한 경우

        최종 index가 10에 도달한 경우

        ➡️  라이언의 점수판의 마지막 인덱스에 남은 화살의 수를 기록한다.

     2. 라이언이 만들 수 있는 점수의 경우의 수는 2가지이다.

        1. ‘어피치가 기록한 점수 + 1’ 점
           • 라이언의 현재 남은 화살의 개수가 ‘어피치가 기록한 점수 + 1’ 점보다 크다면 해당 인덱스의 라이언 점수를 ‘어피치가 기록한 점수 + 1’점으로 기록하고 다음 인덱스로 dfs를 수행한다.
        2. 0점
           • 언제든지 0점을 기록할 수 있으므로 해당 인덱스의 라이언 점수를 0점으로 기록하고 다음 인덱스로 dfs를 수행한다. (라이언의 남은 화살 개수 변동 X)

💬 풀이

import Foundation

var ryanWinInfo: [[Int]] = []
var ryanWinScore: Int = -1

func solution(_ n: Int, _ info: [Int]) -> [Int] {
    let ryanInfo = [Int](repeating: 0, count: 11)
    dfs(n, 0, ryanInfo, info)
    
		// 라이언이 우승할 수 없는 경우
    if ryanWinScore <= 0 {
        return [-1]
    }
    
    ryanWinInfo.sort {
        $0.filter { $0 != 0 }.count > $1.filter { $0 != 0 }.count
    }

    return ryanWinInfo.first!
}

// MARK: - 라이언의 점수판에 점수를 기록하는 dfs 함수
func dfs(_ leftArrow: Int, _ index: Int, _ ryanInfo: [Int], _ appeachInfo: [Int]) {
    var ryanInfo = ryanInfo
    let leftArrow = leftArrow
    
    if index == 10 || leftArrow <= 0 {
        if index == 10 {
            ryanInfo[10] = leftArrow
        }
        
        // 점수차
        let gap = ryanAppeachGap(appeachInfo, ryanInfo)
        
        if gap == ryanWinScore {
            ryanWinInfo.append(ryanInfo)
        } else if gap > ryanWinScore {
            ryanWinScore = gap
            ryanWinInfo = [ryanInfo]
        }
        
        return
    }
    
    if leftArrow > appeachInfo[index] {
        ryanInfo[index] = appeachInfo[index] + 1
        
        let nextLeftArrow = leftArrow - (appeachInfo[index] + 1)
        dfs(nextLeftArrow, index + 1, ryanInfo, appeachInfo)
        ryanInfo[index] = 0
    }
    
    dfs(leftArrow, index + 1, ryanInfo, appeachInfo)
}

// MARK: - 라이언과 어피치의 점수 차를 반환하는 함수
func ryanAppeachGap(_ appeach: [Int], _ ryan: [Int]) -> Int {
    var appeachScore = 0, ryanScore = 0

    for (index, ryan) in ryan.enumerated() {
        if ryan == 0 {
            appeachScore += (appeach[index] > 0 ? (10 - index) : 0)
        } else {
            ryanScore += (10 - index)
        }
    }

    return ryanScore - appeachScore
}

소요시간 : 헤매서 오래 걸렸다.. 중간에 타이머가 날아가서 기록하지 못함