[Programmers] 양궁 대회 (Level 2)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/92342

프로그래머스

문제 요약

라이언과 어피치가 양궁 대결을 합니다. 각각 n발을 쏠 수 있고 0점~10점까지의 점수판이 있습니다.

이 문제에서 특이한 점은 점수 계산 방법입니다. 저희가 아는 양궁경기와 달리, 맞춘 점수의 총합이 아닙니다.

0점부터 10점까지 각각 맞춘 화살의 개수가 더 많은 사람이 해당 점수를 가지게 됩니다. 

 

예를들어, 10점은 어피치가 2번 라이언이 3번 맞추었다면, 

라이언이 점수 10점을 가지게 됩니다. 

만약 어피치가 3번, 라이언도 3번 맞추었다면 

이때는 어피치가 점수를 가지게 됩니다.

 

어피치가 화살을 맞춘 개수가 배열로 주어질 때 라이언이 가장 큰 점수 차이로 우승하기 위해서 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 구해야하는 문제입니다.

풀이

10점~0점까지 모두 알아내야 합니다. 

그리고 최대한 큰 점수 차이를 벌려야합니다.

또, 점수 차이가 같다면 가장 낮은 점수를 더 많이 맞힌 경우를 구해야합니다. (문제요약에서는 설명하지 않은 조건)

 

마지막 조건때문에 0점부터 시작해서 모든 경우의 수를 구해줍니다. 

모든 경우의 수라기보다, (어피치 + 1)번만 맞추면 해당 점수를 획득할 수 있기 때문에 개수를 줄여나가면서 1점..2점..3점 하나씩 계산해주어야 합니다. 

 

첫 풀이에서는 0점부터 시작하지 않았기 때문에, 8번과 18번 케이스를 통과하지 못헀어요.

10점부터 시작해서 매 케이스를 구했고, 점수 차이가 같을 경우 가장 낮은 점수를 맞힌 개수를 비교해서 더 큰 경우를 정답으로 처리했는데 계속 통과하지 못하더라구요. 아직도 반례를 못 찾았습니다. 😓😓😓

 

그래도 계속 생각해보면 0점부터 시작하면 된다는 사실을 알 수 있어요.

1. 큰 점수를 아무리 맞추어도 10점, 9점밖에 획득하지 못하기 때문에 최대한의 큰 점수를 맞추기 위해선 어피치보다 1번 더 맞추면 돼요. 

2. 가장 낮은 점수부터 고려하면 점수 차이가 같은 경우에 낮은 점수를 더 많이 맞추었는지 고려하지 않아도 돼요. 어피치보다 1번 더 맞춘 경우보다 더많이 맞춘 경우는 있을 수 없기 때문입니다. 점수 차이가 같은 경우는 무시해주면 됩니다. 오로지 점수차이가 큰 경우만 새로 업데이트해줍니다.

 

코드

import Foundation

func solution(_ n:Int, _ info:[Int]) -> [Int] {
    var ryanResult: [Int] = []
    var scoreDiff: Int = Int.min
    func dfs(index: Int, count: Int, appeachScore: Int, ryanScore: Int, result: [Int]) {
        if n == count, result.count == info.count, appeachScore < ryanScore {
            if scoreDiff < ryanScore - appeachScore {
                scoreDiff = ryanScore - appeachScore
                ryanResult = result
            }
            return
        }

        if count > n { return }
        if index < 0 { return }

        let score = 10 - index
        for ryanCount in (0...info[index]+1).reversed() {
            if ryanCount == 0, info[index] == 0 {
                dfs(index: index-1, count: count, appeachScore: appeachScore, ryanScore: ryanScore, result: result + [0])
            } else if ryanCount > info[index] {
                dfs(index: index-1, count: count+ryanCount, appeachScore: appeachScore, ryanScore: ryanScore + score, result: result + [ryanCount])
            } else {
                dfs(index: index-1, count: count+ryanCount, appeachScore: appeachScore + score, ryanScore: ryanScore, result: result + [ryanCount])
            }
        }

    }

    dfs(index: 10, count: 0, appeachScore: 0, ryanScore: 0, result: [])

    return ryanResult.isEmpty ? [-1] : ryanResult.reversed()
}