[JS] 금과 은 운반하기 - 파라메트릭 서치 접근법 심화

이 문제는 뭔가 이진 탐색을 써야할 것 같은 느낌이 딱 오는데..

뭔가 어떻게 최댓값을 설정해야할 지 감이 안옵니다.

어떻게 이렇게 이해했는지 천천히 설명해보겠습니다

---

문제 요약

어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 a kg과 은 b kg이 전달되어야 합니다.

각 도시에는 번호가 매겨져 있는데, i번 도시에는 금 g[i] kg, 은 s[i] kg, 그리고 트럭 한 대가 있습니다. i번 도시의 트럭은 오직 새 도시를 짓는 건설 장소와 i번 도시만을 왕복할 수 있으며, 편도로 이동하는 데 t[i] 시간이 걸리고, 최대 w[i] kg 광물을 운반할 수 있습니다. (광물은 금과 은입니다. 즉, 금과 은을 동시에 운반할 수 있습니다.) 모든 트럭은 같은 도로를 여러 번 왕복할 수 있으며 연료는 무한대라고 가정합니다.

정수 a, b와 정수 배열 g, s, w, t가 매개변수로 주어집니다. 주어진 정보를 바탕으로 각 도시의 트럭을 최적으로 운행했을 때, 새로운 도시를 건설하기 위해 금 a kg과 은 b kg을 전달할 수 있는 가장 빠른 시간을 구해 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 0 ≤ a, b ≤ 109
• 1 ≤ g의 길이 = s의 길이 = w의 길이 = t의 길이 = 도시 개수 ≤ 105
  • 0 ≤ g[i], s[i] ≤ 109
  • 1 ≤ w[i] ≤ 102
  • 1 ≤ t[i] ≤ 105
  • a ≤ g의 모든 수의 합
  • b ≤ s의 모든 수의 합

테스트케이스

a	b	g	s	w	t	result
10	10	[100]	[100]	[7]	[10]	50
90	500	[70,70,0]	[0,0,500]	[100,100,2]	[4,8,1]	499

 

접근 방법

예전에 파라메트릭 서치를 한 번 다룬 적이 있습니다.입국 심사라는 문제였는데요.

[JS] 입국심사 - 왜 이게 이진 탐색인지 알려드림

 

해당 문제와 결이 유사합니다.

엄청나게 큰 a, b 값이라는 점과 특정 조건에서 최솟값을 구해야하는 것도 같습니다.

 

입국심사 문제에선 심사를 마치는 최소 시간을 return 해야했습니다.

이때 우리는 사람을 소숫점 단위로 계산 할 수 없기에 Math.floor를 써서 계산을 해냈었죠.

이 문제는 변수가 하나만 있던(심사관 당 처리 시간) 위 문제와 다르게 금과 은이라는 두 변수를 함께 조작하는 이진탐색입니다.

 

기본적인 골자는 같으나, 나올 수 있는 최댓값을 설정하는데 있어서 막막함이 있습니다.

저는 이런 식으로 설정해봤습니다 

// 현재 (자원 * 시간) / 무게을 의미합니다.
// 자원은 금과 은의 합을 의미합니다.
// 시간은 왔다 갔다 두 번을 같이 계산합니다.
// 최소 무게인 1로 정할 때 가장 트럭이 많이 움직이게 됩니다.
// 따라서 무게를 1로 정한 해당 값을 최대로 합니다.
let [start, end] = [0, 10e9 * 2 * 10e5 * 2];

 

다른 블로그나 포스트에서 검색해보면 특히 이 설정이 틀리게 적혀있는 곳이 많더라구요.

무게를 곱해주는게 아니라 나눈다고 생각하면 이해가 훨씬 쉽습니다.

 

정답 코드

function solution(a, b, g, s, w, t) {
    // 현재 자원(금 + 은) * 시간
    let [start, end] = [0, 10e9 * 2 * 10e5 * 2];
    let mid = Math.floor((start + end) / 2);
    const totalVilage = g.length;
    
    while (start <= end) {
        let [gold, silver, resource] = [0, 0, 0];
        
        for (let i = 0; i < totalVilage; i++) {
            const remainResource = Math.round(mid / (2 * t[i]));
            const maxCarryingResource = remainResource * w[i];
            gold += Math.min(g[i], maxCarryingResource);
            silver += Math.min(s[i], maxCarryingResource);
            resource += Math.min(g[i] + s[i] , maxCarryingResource);
        }
        
        if (gold >= a && silver >= b && resource >= (a + b)) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
        mid = Math.floor((start + end) / 2);
    }
    
    return start;
}

실행 결과

 

팁 1. resource로 따로 관리해주는 이유가 뭔가요?

// mid: [kg * 시간 / 트럭의 단위 무게];
// remainResource: [kg / 트럭의 단위 무게];
// maxCarryingResource: [kg];

const remainResource = Math.round(mid / (2 * t[i]));
const maxCarryingResource = remainResource * w[i];
gold += Math.min(g[i], maxCarryingResource);
silver += Math.min(s[i], maxCarryingResource);
resource += Math.min(g[i] + s[i] , maxCarryingResource);

 

 

일단 maxCarryingResource가 한 번에 들고 갈 수 있는 어떤 자원의 무게라고 이해가 되었으리라 믿습니다...!

그런데 이 무게가 어떤 자원에 대한 건지 우린 알 수가 없습니다.

maxCarryingResource가 초기의 엄청 큰 값일 때는 문제가 되지 않지만,

만약 해당 값이 a + b보다 작은 값이 된다면, (= 트럭이 꽉꽉 담아가지 않는다면) 최소 시간을 보장 받을 수 없습니다.

최소 시간으로 모든 자원을 옮기기 위해서는 매번 트럭을 꽉꽉 채워서 나가야할 테니까요.

그걸 비교하기 위해 해당 값을 비교해줍시다.

---

구현한 코드가 짧은데 비해서 정말 오랫동안 고민했습니다.

이진 탐색을 쓰는 건 대충 눈치를 챘었는데, 어떤 값을 기준으로 이진탐색을 돌려야하는가? 에 대해서 고민을 오래했네요.

 

어렵습니다..ㅠ

그럼 이만!