[Programmers] (그리디. Greedy) Lv 2. 광물 캐기

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

프로그래머스

 

곡괭이를 어떤 순서로 사용하든, 캐는 광석의 양은 동일하다. 그저 사용 순서에 따라 피로도가 달라질 뿐이다.
그렇다면 'N = 광석의 총 개수', 'M = 총 곡괭이의 개수'라고 했을 때, [0, min(N, 5M) - 1] 범위의 광석을 순서대로 캐게 될 거란 건 변함이 없다. 그리고 어떤 곡괭이를 사용하면 무조건 5개를 연속으로 캐야 하니까 5개씩 묶음으로 생각해 볼 수 있다.

아래 예제로. 편의상 d = 다이아, r = 철, s = 돌 이라고 생각해보고
picks = [1, 1, 2]
minerals = [r, r, r, r, d, d, d, d]
이 상태에서 미네랄을 5개씩 묶으면, [[r, r, r, r, d], [d, d, d]] 가 된다.
이 묶음들에게 최적의 곡괭이를 부여한다고 생각했을 때, [r, r, r, r, d] -> 1번(철 곡괭이), [d, d, d] -> 0번(다이아 곡괭이)일 때,
피로도를 가장 최소로 하는 경우이다.
위의 관찰을 통해, 각 묶음들에 대하여 다이아가 많을 수록, 다이아 개수가 같다면 철이 많을 수록 성능이 좋은 곡괭이(0번에 가까운)를 사용해야 한다는 탐욕적 속성을 찾을 수 있다.

 

이를 귀류법으로 증명보자.
가정 - 각 묶음들에 대하여 다이아가 많을 수록, 다이아 개수가 같다면 철이 많을 수록 성능이 좋은 곡괭이를 우선으로 사용하는 최적해가 존재한다.
증명 - 성능이 안 좋은 곡괭이를 우선으로 사용하는 최적해가 존재한다고 하자.
묶음 a와 묶음 b에 대해 다음과 같은 상황을 가정할 수 있다. (a >= b, a가 b보다 다이아나 철의 개수가 같거나 많다.)
a - 1번 곡괭이, b - 0번 곡괭이
이 상황에서 앞선 가정으로 곡괭이를 사용해도 최적해가 보장된다는 걸 알 수 있다.
a - 0번 곡괭이, b - 1번 곡괭이
이유는 0번 곡괭이가 a를 처리하든 b를 처리하든 피로도는 5로 같지만, 1번 곡괭이가 b를 처리할 때보다 a를 처리할 때 최소 0이상의 피로도를 더 소모한다. 왜냐하면 a의 다이아 개수 >= b의 다이아 개수 이기 때문이다. (a의 다이아 개수 > b의 다이아 개수라면 최소 5이상의 피로도를 더 소모한다.)
고로 앞선 가정으로 탐욕적 속성을 선택해도, 최적해를 보장할 수 있다.

증명에선 0번과 1번 곡괭이만 예시로 들었는데, 다른 곡괭이를 대입해봐도 결과는 같다.
그렇다면 위의 기준을 통해 정렬을 해서 순서를 강제시킬 수 있다. 아까 예제를 그대로 들고 와서 정렬해자.
[[r, r, r, r, d], [d, d, d]] -> [[d, d, d], [r, r, r, r, d]]
이렇게 정렬할 수 있고, 앞에서부터 묶음들에 대해 최대한 좋은 곡괭이로 처리시키면 최적해를 구할 수 있다.

정리하자면 전체 로직을 이렇게 정리할 수 있다.

1. 앞에서부터 최대 M개의 광석 묶음을 만든다. (M은 곡괭이의 총 개수)
2. 광석 묶음을 내림차순으로 정렬한다. (다이아가 많은 순, 다이아가 같다면 철이 많은 순)
3. 앞에서부터 최대한 좋은 곡괭이로 묶음을 처리한다.

// 완전 탐색으로도 풀 수 있지만, 그리디로 해결
// 1. 자원을 5개씩 묶는다.
// 2. 묶는 자원 별로 각 광물끼리 수를 저장한다.
// 3. 비용이 큰 순서대로 정렬하고, 다이아 곡괭이 -> 철 곡괭이 -> 돌 곡괭이 순으로 광물을 캐면 된다.
function solution(picks, minerals) {
    let answer = 0;

    const bundle = Math.min(picks.reduce((acc, e) => acc + e, 0) * 5, minerals.length); // 광석을 캐는 실제 범위
    const arr = minerals.reduce((acc, e, idx) => { // 5개씩 그룹화
        if (idx >= bundle) return acc;

        const i = ~~(idx / 5); // 5개씩 묶는 형태
        acc[i] = acc[i] || [0, 0, 0];
        ++acc[i][["diamond", "iron", "stone"].indexOf(e)];
        return acc;
    }, []);

    // 다이아 광물이 제일 많은 순이 최우선
    // 그 다음으로, 다이아 광물이 같다면 철 광물이 최우선
    // 결론은 비용이 가장 많이 드는 순으로 정렬한다. (다이아 곡괭이부터 쓸것이기 때문에)
    arr.sort((a, b) => b[0] - a[0] || b[1] - a[1]);

    arr.forEach((e) => {
        for (let i = 0; i < picks.length; ++i) {
            if (!picks[i]) continue; // 곡괭이 수가 0인 것은 pass

            e.forEach((el, idx) => {
                if (idx < i) answer += Math.pow(5, i - idx) * el; // 광물이 곡괭이보다 속성이 높다면, 그 차이만큼 5의 거듭제곱으로 피로도 누적
                else answer += el;
            })
            --picks[i];

            return; // 곡괭이를 썻으니, 다음 광물묶음에 새로운 곡괭이로 체크하기위해 바로 return
        }
    });

    return answer;
}

GitHub : https://github.com/developeSHG/Algorithm-Baekjoon_Programmers/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/unrated/172927.%E2%80%85%EA%B4%91%EB%AC%BC%E2%80%85%EC%BA%90%EA%B8%B0/%EA%B4%91%EB%AC%BC%E2%80%85%EC%BA%90%EA%B8%B0.js

GitHub - developeSHG/Algorithm-Baekjoon_Programmers: 백준 and 프로그래머스 소스코드