[프로그래머스] 금과 은 운반하기 (C++)

문제

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

아이디어1

파라매트릭 서치

• 조건을 통해 원하는 값을 찾아감

long long start = 0;
long long end = 2 * 1e9 * 2 * 1e5;

• 시간의 범위는 0 부터 4 * 1e14;
  • 금속 종류 $\times$ 최대 금속 보유량 $\times$ 왕복 $\times$ 최대 이동 시간 $\times$ 최소 운반 무게
  • $2 \times 10^9 \times 2 \times 10^5 \times 1$

while(start + 1 < end)
{
    long long total = 0;
    long long gold = 0;
    long long silver = 0;

    long long mid = (start + end) / (long long)2;

    for (int i = 0; i < g.size(); ++i)
    {
        long long times = mid / t[i];
        times = (times >> 1) + (times & 1);

        long long weight = times * w[i];
        total += min(weight, (long long)g[i] + (long long)s[i]);
        gold += min(weight, (long long)g[i]);
        silver += min(weight, (long long)s[i]);
    }

    if ((total >= a + b) && (gold >= a) && (silver >= b))
        end = mid;
    else
        start = mid;
}

return end;

• 범위를 절반씩 줄여가며 주어진 시간에 금속을 전달할 수 있는지 판단
  • 전달할 수 있다면 상한 범위를 줄여줌
  • 전달할 수 없다면 하한 범위를 줄여줌
• 금과 은, 금, 은을 각각 최대로 옮길 수 있는 양을 구해 조건을 만족하는지 판단
  • 주어진 시간 동안 전달 가능한 횟수와 한 번에 옮길 수 있는 무게와 보유량 중 작은 값
    • 횟수는 왕복 + 편도(0 ~ 1번)