86053. 금과 은 운반하기

2026-01-31
programmers
프로그래머스 86053번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

코딩테스트 연습 - 금과 은 운반하기 | 프로그래머스 스쿨

풀이

아이디어

이 문제는 이분탐색으로 풀어야 한다!

이 문제는 답을 구하는 문제가 아닌 답인지 아닌지를 확인하는 문제이다. 무슨말이냐면, 어떤 경로를 거쳐야 최단 시간 안에 운송할 수 있는지를 구하는게 아닌, 어떤 시간 안에 어떻게든 운송이 가능한지만을 확인하는 문제라는 것이다.

그리고 단조성을 띈다. 단조성은 어떤 시점을 기준으로 가능/불가능, 정답/오답이 갈리는 특징을 말한다. 이 문제 역시 아래와 같은 특징을 가지므로 단조성을 갖고 있다.

  • 어떤 시간 Time에서 운송이 가능하면 그보다 더 큰 시간들에서는 (가능한 트럭의 왕복 횟수가 증가하기 때문에) 무조건 시간 안에 운송이 가능하다.
  • 어떤 시간 Time에서 운송이 불가능하면, 그보다 더 작은 시간들에서도 (가능한 트럭의 왕복 횟수가 감소하기 때문에) 시간 안에 운송이 불가능하다.

따라서 이 문제는 이분탐색으로 풀어야 한다!

운반 가능 여부 확인하는 check 함수 구현하기

check(time) 함수는 time 시간이 주어졌을 때 운반이 가능한지를 확인하는 함수이다.

check 함수에서 확인해야 하는 조건은 아래 3가지 조건이다.

  1. 모든 도시에서 time 시간 안에 실을 수 있는 금의 총 합 >= a (필요한 금의 양)
  2. 모든 도시에서 time 시간 안에 실을 수 있는 은의 총 합 >= b (필요한 은의 양)
  3. 모든 도시에서 time 시간 안에 실을 수 있는 광물(금과 은)의 총 합 >= a + b

1번, 2번 조건은 금이나 은 자체가 부족한 경우를 막는 조건이다. time 시간 안에 트럭은 충분히 운송할 수 있더라도 전체 도시들에 있는 총량이 필요한 양보다 작으면 불가능하기 때문에 이 부분을 체크하기 위한 조건이다.

마지막 3번 조건은 트럭이 두 광물을 동시에 실어야 하기 때문에 확인해야 하는 조건이다. 1번, 2번 조건을 확인할 때에는 같은 트럭 용량을 두 조건이 각각 최대로 사용하고 있기 때문에, 동시에 싣는 것이 불가능할수도 있다. 따라서 동시에 가능한지도 함께 확인하는 것이다.

그래서 check(time)의 구조는 모든 도시를 돌면서 아래 3가지를 구해서 확인하는 식으로 되어 있다.

  1. 그 도시가 time 시간 안에 새 도시에 보낼 수 있는 최대 금
  2. 그 도시가 time 시간 안에 새 도시에 보낼 수 있는 최대 은
  3. 그 도시가 time 시간 안에 새 도시에 보낼 수 있는 최대 광물

이것을 구하려면 time 시간 안에 트럭이 몇번 새 도시에 도착할 수 있는지를 구해야 하는데, 중요한 것은 운반이 “도착” 시점에 이뤄진다는 것이다. 그래서 기본적으로는 왕복 시간을 이용해서 횟수를 구하되, 딱 한번 새 도시로 편도로 갈 수 있는 여유 시간이 남는다면 한번 더 운송하도록 해야 한다. 코드로 구현하면 아래와 같다.

const maxDeliveries = Math.floor(time / (2 * t[i])) + (time % (2 * t[i]) >= t[i] ? 1 : 0);

이분탐색 구현하기!

check 함수까지 구현했으니 이제 이분탐색만 하면 된다. 이건 간단하니까 그냥 코드만 남겨둔다.

// 이분탐색
let left = 0, right = 10 ** 15;
while (left < right) {
	const mid = Math.floor((right + left) / 2);
	if (check(mid)) right = mid;
	else left = mid + 1;
}

코드

function solution(a, b, g, s, w, t) {
    // time 시간 안에 모든 도시에서 필요한 광물들을 운반할 수 있는지를 확인
    function check(time) {
        const cityCount = g.length;
        let gold = 0, silver = 0, total = 0;
        for (let i = 0; i < cityCount; i++) {
            // time 시간 안에 "운반"할 수 있는 최대 횟수
            const maxDeliveries = Math.floor(time / (2 * t[i])) + (time % (2 * t[i]) >= t[i] ? 1 : 0);
            // time 시간 안에 운반할 수 있는 광물의 최대 양
            const cap = maxDeliveries * w[i];

            gold += Math.min(g[i], cap);
            silver += Math.min(s[i], cap);
            total += Math.min(g[i] + s[i], cap);
        }

        return gold >= a && silver >= b && total >= a + b;
    }

    // 이분탐색
    let left = 0, right = 10 ** 15;
    while (left < right) {
        const mid = Math.floor((right + left) / 2);
        if (check(mid)) right = mid;
        else left = mid + 1;
    }

    return left;
}

이진탐색 문제 재밌다… 취향에 맞음