Level 2️⃣ - 디펜스 게임

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

프로그래머스

문제 접근

차례대로 라운드가 진행된다는 점을 주의해야한다.

1. 전체 라운드 중에서 무적권을 사용할 수 있는 k개를 뽑는다. 이 말은 enemy 중에서 k개를 뽑는 것과 같다. 그리고 해당 라운드에서는 무적권을 사용한다는 표시를 해둔다.
2. 무적권을 사용하지 않는 라운드도 표시를 한다.
3. 무적권을 사용하지 않는 라운드에서만 병사를 소모한다.
4. 최대 진행할 수 있는 라운드 수를 구한다. 

위의 절차에 따라 다음과 같은 코드를 구현했다. 하지만 결과는 시간 초과가 나왔다. n의 범위가 10억이고 k의 범위가 50만이기 때문에 재귀를 활용한 조합으로 해결하기에는 당연히 시간 초과가 나올 수 밖에 없다.

시간복잡도 O(N) 알고리즘을 생각해야한다.

function solution(n, k, enemy) {
    let max = Number.MIN_SAFE_INTEGER;
    
    function combi(start, b){
        if(b.length === k){
            let cnt = n;
            let round = 0;
            const tmp = enemy.map((elem, idx)=>{
                if(b.includes(idx)) return [elem, 'guard'];
                return [elem, 'noGuard'];
            });
            if(tmp.every((elem)=> elem[1] === 'guard')) {
                max = enemy.length;
                return;
            }
            for(const elem of tmp){
                const [e, flag] = elem;
                if(flag === 'noGuard') cnt -= e;
                if(cnt < 0) {
                    max = Math.max(max, round);
                    break;
                }
                round += 1;
            }
        }
        else{
            for(let i = start+1; i<enemy.length; i++){
                b.push(i);
                combi(i, b);
                b.pop();
            }
        }
    }
    
    combi(-1, []);
    
    return max;
}

 

혼자 고민하다가 도저히 해답을 모르겠어서 여러 블로그를 참고했고, 이진 탐색을 통해 구현하는 방법이 있었다.

정확하게는 이진 탐색을 활용한 결정 알고리즘이다. 결정 알고리즘은 이진 탐색을 통해 최대 또는 최소를 결정하는 알고리즘이다.

결정 알고리즘에서 가장 중요한 것은 "무엇을 결정할 것인가." 를 명확하게 짚어야한다.

진행할 수 있는 최대 라운드 수를 구해야하기 때문에 우리가 결정해야하는 것은 차례대로 라운드를 진행하였을 때 어디까지 진행할 수 있는가를 결정해야한다. 이 부분을 이진 탐색으로 구해보겠다는 것이다.

function solution(n, k, enemy) {
    let [left, right] = [0, enemy.length];
    let ret = 0;
    while(right >= left){
        let mid = Math.floor((left + right) / 2);
        // mid 직전까지 라운드를 진행한다. 
        // 최대 라운드를 진행하기 위해서는 적의 수가 많은 것부터 무적권을 사용해야하므로 내림차순 정렬 
        const curSlice = enemy.slice(0, mid).sort((a,b)=>b-a); 
        let noDie = k;
        const curEnemy = curSlice.reduce((acc,cur)=>{
        // 무적권이 있으면
            if(noDie > 0){
                noDie -= 1;
                return acc;
            }
            return acc + cur;
        }, 0);
        // 무적권 한도 내에서 적군을 모두 처치할 수 있는지를 확인한다.
        if(n - curEnemy >= 0 && noDie >= 0){
            ret = curSlice.length; // 현재 라운드 수를 저장한다.
            left = mid + 1; // 라운드 수를 늘려준다.
        }
        else{
            right = mid - 1;
        }
    }
    return ret;
}