[프로그래머스 92342] 양궁 대회 swift

프로그래머스

 

 

문제 설명

 

 

문제 풀이

 

첨에 무식하게 DFS로 화살의 합이 n이 되는 모든 경우를 구했다.

 

ex) n이 3이면

[3,0,0,0,0,0,0,0,0,0,0]

[2,1,0,0,0,0,0,0,0,0,0]

[0,3,0,0,0,0,0,0,0,0,0]

[0,2,1,0,0,0,0,0,0,0,0]

...

 

n이 9를 넘어가니까 시간초과..

 

결국 정답을 살짝 보고 다시 구현해 보았다.

 

핵심은 

어피치를 이기는 경우 / 지는 경우로 나누는 것

 

어피치의 화살이

[2,3,1,0,0,0,0,1,3,0,0]

일 때

 

어피치를 이기는 경우

0번째 인덱스(10점)을 이기는 경우는 라이언이 3발을 쏘았을 때다. (여기서 4발 이상 쏘면 화살 낭비로 의미가 없다.)

 

어피치를 지는 경우

어차피 질 거 화살 낭비 없이 0개로 진다.

 

 

이 경우로 DFS를 돌려준다.

 

DFS(현재인덱스(=깊이), 화살의 총합, 화살 리스트)

로 돌리며

 

깊이가 10이 되었거나 화살을 다 썼을 때 DFS를 종료시킨다.

그리고 만약에 화살이 남았는데 종료 되었으면 남은 화살을 0점에 몰아넣는다. (점수차가 같을 경우 낮은점수에 화살이 많은게 유리하므로)

 

 

코드

func solution(_ n:Int, _ info:[Int]) -> [Int] {
    
    // 어피치와 나의 점수 차이를 리턴
    func getScoreDiff(_ arr: [Int]) -> Int {
        var apeachScore = 0
        var lionScore = 0
        for i in 0..<11 {
            if arr[i] == 0 && info[i] == 0 {
                continue
            }
            if arr[i] > info[i] {
                lionScore += (10-i)
            }
            else {
                apeachScore += (10-i)
            }
        }
        return lionScore - apeachScore
    }
    
    // 더 낮은 점수의 화살이 있으면 true 리턴
    func isMoreThanLowScore(answer: [Int], arr: [Int]) -> Bool {
        for i in stride(from: 10, through: 0, by: -1) {
            if answer[i] < arr[i] {
                return true
            }
            else if answer[i] > arr[i] {
                return false
            }
        }
        return false
    }
    
    var answer = Array(repeating: 0, count: 11)
    var maxScore = 0
   
    func DFS(depth: Int, arrowCount: Int, arr: [Int]) {
        // 끝까지 돌았거나 화살을 다 썼을 경우
        if arrowCount == n || depth == 10 {
            var arr = arr
            
            // 남은 화살이 있다면 그 화살을 0점에 다 넣어줌
            if arrowCount < n {
                arr[10] = n-arrowCount
            }
            
            let score = getScoreDiff(arr) // 점수 차이를 구함
            
            // 점수 차이가 더 크면 정답을 바꿈
            if maxScore < score {
                maxScore = score
                answer = arr
            }
            
            // 현재 정답과 점수차이는 똑같지만 낮은 점수판의 화살이 더 많으면 정답 바꿈
            else if maxScore == score && isMoreThanLowScore(answer: answer, arr: arr) {
                answer = arr
            }
        }
        else {
            let apeachWinCount = info[depth] + 1 // 어피치를 이길 수 있는 개수
            
            // 지금 어피치를 이길 수 있는 화살이 남아있다면
            if apeachWinCount+arrowCount <= n {
                var arrWin = arr
                arrWin[depth] = apeachWinCount
                // 어피치를 이기는 경우 DFS
                DFS(depth: depth+1, arrowCount: arrowCount+apeachWinCount, arr: arrWin)
            }
            
            // 어피치를 지는 경우 DFS (0으로 진다.)
            DFS(depth: depth+1, arrowCount: arrowCount, arr: arr)
        }
    }
    DFS(depth: 0, arrowCount: 0, arr: [0,0,0,0,0,0,0,0,0,0,0])
    
    return maxScore == 0 ? [-1] : answer
}

 

 

후기

 

푸는데 정말 오래 걸렸다... 처음에 1시간정도 써서 풀었고

시간초과 난뒤로 어떻게든 오기로 풀어보려다가.. 산으로 감

 

결국 정답보고 잘못된 접근이었음을 깨달았다.

하루 이상 투자하면 답을 보자