[JS] 양궁대회

일종의 완전탐색 기법으로 문제를 해결하였다.

 

화살이 최대 10개이고 모든 경우의수를 단순히 조합으로 구하는게 아니라 순열 형식으로 구하는 거라서 경우의 수가 크게 안나올 것이라 생각하여 10개를 쏘았을때 맞출수 있는 모든 경우의 수를 구하였고 실제로 10개의 화살을 쏘았을때 10만개의 경우의 수가 되지 않았다.

 

이어서 점수를 구하는 함수를 사용하고 만약 가장 낮은 점수가 같을때 개수를 비교할 수 있는 로직을 추가해주어서 해결하였다.

 

 

1. 화살 n개로 나올 수 있는 모든 경우의수를 재귀함수로 구하기

2. 점수를 계산해서 점수의 차가 가장 큰 경우에는 바꿔주기

3. 점수 차가 똑같은 경우 가장 낮은 점수의 개수를 통해서 정답 정해주기

4. 정답이 없다고 [-1]을, 정답이 있다면 해당 정답 반환하기

 

 

 

 

 

모든 경우의수를 구하는 로직에서는 순열을 구하는 로직을 약간 변형해서 구해보았다. 결국 합계가 10이 되어야 하고, 0~10까지 각 수가 올 수 있는데 합계가 10이 넘어가는 부분들은 생략함으로써 경우의수를 많이 줄여주었다.

 

const combination = (arr,n,step,sum) =>{
    
    if(step===10) return [[...arr , n-sum]]
    
    let ret = []
    for (let i = 0 ; i<=n-sum ; i++) {
        if (sum+i > n) break
        const attached = combination([...arr,i],n,step+1,sum+i)
        ret.push(...attached)
    }
    return ret
}

const getScore = (lion,apeach) => {
    let lionScore = 0
    let apeachScore = 0
    for (let i = 0 ; i< 11 ; i ++) {
        if (!lion[i] && !apeach[i]) continue
        if (lion[i] > apeach[i]) lionScore += 10-i
        else apeachScore += 10-i
    }
    
    if (apeachScore >= lionScore) return false
    else return lionScore-apeachScore
}

const getLastNonZeroIdx = (arr) => {
    for (let i = arr.length-1 ; i >= 0 ; i --){
        if (arr[i] !== 0) return i
    }
    return undefined
}

function solution(n, info) {
    
    let ret = []
    let diff = 0
    for (const ary of combination([],n,0,0)){
        const scoreDiff = getScore(ary,info)
        if (!scoreDiff) continue
        if (scoreDiff > diff) {
            ret = ary
            diff = scoreDiff
        } else if(scoreDiff === diff) {
            const aryIdx = getLastNonZeroIdx(ary)
            const retIdx = getLastNonZeroIdx(ret)
            if (retIdx < aryIdx) ret = ary
            else if (retIdx===aryIdx && ret[aryIdx] < ary[aryIdx]) ret= ary
            
        }
    }
    
    return ret.length ? ret : [-1]
}