[프로그래머스 C#] Lv.3 금과 은 운반하기

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

주어진 도시에 있는 자원들을 운반해 새로운 도시를 짓기 위해 필요한 최소 시간을 구하는 문제

- 각 도시에 있는 금, 은 무게와 트럭에 한번에 적재 가능한 무게, 편도 이동 시간이 주어짐

- 트럭은 도시마다 1대씩만 존재하며, 동시 운행이 가능

- 최초 1회 운송만 편도 시간이 들고, 이후에는 왕복 시간으로 연산해야 함

 

시간 안에 모든 자원을 옮길 수 있는지 판단

- 각 도시에서 옮길 수 있는 자원의 누적합을 이용

 -> 시간 안에 옮길 수 있는 총 자원 무게, 최대 금 무게, 최대 은 무게

 -> 도시를 짓기 위해 필요한 무게를 비교

  즉, 세 가지 조건이 모두 만족한다면, 시간 안에 모든 자원을 옮길 수 있음

 

이분 탐색

- 시간 안에 도시를 짓기 위한 자원을 모두 옮길 수 있는지 판단

 -> 모든 자원을 옮기기 위한 최대 시간을 구하여 이분 탐색의 거리를 측정

 

주석 참조

    using System;

    public class Solution
    {
        public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t)
        {
            // 이분 탐색을 위한 최소 시간과 최대 시간 범위
            long minTime = 1;
            long maxTime = 1;

            // 모든 도시의 자원을 옮기기 위해 걸리는 최대 시간 세팅
            for (int i = 0; i < g.Length; i++)
            {
                long weight = g[i] + s[i]; // 총 무게
                long count = weight / w[i]; // 운반 횟수
                if (0 < weight % w[i])
                    count++;
                    
                long time = 2 * t[i] * count; // 걸리는 시간
                maxTime = Math.Max(maxTime, time);
            }

            // 이분탐색
            while (minTime <= maxTime)
            {
                long midTime = (minTime + maxTime) / 2;
                
                // 모든 자원을 얻을 수 있는 시간인가?
                if (Function(a, b, g, s, w, t, midTime))
                    maxTime = midTime - 1;
                else
                    minTime = midTime + 1;
            }

            return maxTime;
        }

        // 해당 시간 안에 새 도시를 짓기 위한 자원을 모두 운반할 수 있는지 여부
        public bool Function(int a, int b, int[] g, int[] s, int[] w, int[] t, long time)
        {
            // 시간 안에 이동시킬 수 있는 최대 광물 무게
            long total = 0; // 금 + 은
            long totalG = 0; // 금
            long totalS = 0; // 은

            for (int i = 0; i < g.Length; i++)
            {
                // 시간 안에 옮길 수 있는 최대 무게
                long maxWeight = (time / (2 * t[i])) * w[i];
                if (t[i] < time % (2 * t[i]))
                    maxWeight += w[i];

                // 누적 최대 광물 무게
                total += Math.Min(g[i] + s[i], maxWeight);
                totalG += Math.Min(g[i], maxWeight);
                totalS += Math.Min(s[i], maxWeight);
            }

            return (a + b <= total) && a <= totalG && b <= totalS;
        }
    }