프로그래머스 - 금과 은 운반하기

[level 3] 금과 은 운반하기 - 86053

문제 링크

성능 요약

메모리: 4.15 MB, 시간: 0.01 ms

구분

코딩테스트 연습 > 월간 코드 챌린지 시즌3

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2024년 03월 26일 16:56:28

문제 설명

어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 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 ≤ 10⁹
• 1 ≤ g의 길이 = s의 길이 = w의 길이 = t의 길이 = 도시 개수 ≤ 10⁵
  • 0 ≤ g[i], s[i] ≤ 10⁹
  • 1 ≤ w[i] ≤ 10²
  • 1 ≤ t[i] ≤ 10⁵
  • 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

---

입출력 예 설명

입출력 예 #1

• 도시가 오직 하나뿐이므로, 0번 도시의 유일한 트럭이 모든 운반을 해결해야 합니다. 이 트럭은 최대 7kg만큼의 광물을 운반할 수 있으며 편도 완주에는 10시간이 걸립니다.
• 맨 처음에 10시간을 써서 7kg만큼의 금을 운반하고, 10시간을 써서 다시 도시로 돌아오고, 10시간을 써서 7kg만큼의 은을 운반하고, 10시간을 써서 다시 도시로 돌아오고, 마지막으로 10시간을 써서 3kg만큼의 금과 3kg만큼의 은을 운반하면, 총 50시간 만에 필요한 모든 금과 은을 조달할 수 있습니다.
• 따라서, 50을 return 해야 합니다.

입출력 예 #2

• 도시가 3개이고, 0번과 1번 도시는 금만 70kg씩 가지고 있고 2번 도시는 은을 500kg 가지고 있습니다.
  • 0번 도시의 트럭은 용량은 100kg, 편도 완주 시간은 4시간입니다.
  • 1번 도시의 트럭은 용량은 100kg, 편도 완주 시간은 8시간입니다.
  • 2번 도시의 트럭은 용량은 2kg, 편도 완주 시간은 1시간입니다.
• 금은 0번 도시의 트럭과 1번 도시의 트럭이 각각 45kg씩 나누어서 운반하면 8시간 안에 필요한 모든 금을 조달할 수 있습니다.
• 은은 2번 도시의 트럭이 한 번에 2kg씩 250번 운반하면(249번 왕복 + 1번 편도) 총 499시간 만에 필요한 모든 은을 조달할 수 있습니다.
• 따라서, 499를 return 해야 합니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

풀이과정

이제 이분탐색에 어느정도 익숙해졌다고 느낄 때마다 익숙해지지 않는 문제들이 나온다.
딱 봤을 때 이거 이분탐색이네 싶은 문제들이 있는데 이번에는 그렇지 않아서 다른 사람의 풀이를 참고할 수밖에 없었다. 많이 풀어보는 수밖에 없겠지...
(엄연히 따지자면 파라메트릭 서치이다. 이분탐색은 특정값을 찾았을 때 바로 리턴한다. 파라메트릭 서치는 특정 조건을 만족하고도 범위가 하나로 좁혀질 때까지 계속 탐색한다. 하지만 귀찮으니 이분탐색이라고 할 거다.)

특정한 무게를 만족하도록 하는 최소 시간을 찾는 것이므로 이분탐색을 생각해볼 수 있다. 이분탐색에서 탐색하는 값은 시간이 되고, 그 시간에서 특정한 무게를 만족할 수 있다면 시간을 줄일 수 있고, 만족할 수 없다면 시간을 늘려야한다.

범위 설정하기

제한사항에 의해서 a, b는 최대 10^9이고, t[i]는 최대 10^5이다.
2(a,b) x 10^9 x 2(왕복) x 10^5 일 때 소모되는 시간이 최대가 된다.
고로 이분탐색의 범위는 st = 0, en = 4* 10^14로 초기화된다.

특정 조건 만족 시 범위 바꾸기

이분탐색에서는 중간값 m = (st+en)/2 에 대해서 조건에 의해 st를 m+1로 늘리거나, en을 m으로 줄인다.
st가 en보다 작은 동안에 계속 반복한다.

조건 만들기

chk 함수에 해당하는 부분이다.

조건은 다음과 같다.

1. 시간 내에 운반할 수 있는 모든 무게가 a+b 보다 크거나 같다.
2. 시간 내에 운반할 수 있는 금의 무게가 a보다 크거나 같다.
3. 시간 내에 운반할 수 있는 은의 무게가 b보다 크거나 같다.

조건을 만족한다면 시간을 줄일 수 있으므로 en=m으로 줄인다.

조건을 좀 더 상세하게 만들어보자.

한 도시에서 트럭이 운반할 수 있는 횟수

cnt는 광물에 접근할 수 있는 횟수이다. 광물을 가져다놓고 다시 운반하려면 왕복해야하므로 왕복 횟수를 세야한다.

cnt = (m / (2 * t[i]))

만약 왕복을 하고도, 편도를 한 번 더 할 수 있다면 마지막 편도 한 번으로 광물을 가져다놓고 끝낼 수 있다.

if(m % (2* t[i]) >= t[i]) cnt++;

누적합

1. 각 도시마다 최대로 나를 수 있는 무게의 누적합을 해준다.

   max_w = min(cnt * w[i], g[i]+s[i]); // 이 도시에서 나를 수 있는 최대 무게
   sum += max_w;

2. 각 도시마다 최대로 나를 수 있는 금무게의 누적합을 해준다.

   sum_g += min(max_w, g[i]);

3. 각 도시마다 최대로 나를 수 있는 은무게의 누적합을 해준다.

   sum_s += min(max_w, s[i]);

리턴하기

조건 만들기에서 만들었던 조건을 만족한다면 true를 리턴해주자.
return (sum >= a+b && sum_g >= a && sum_s >=b);

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#define ll long long

using namespace std;

int n;
bool chk(ll &m, int &a, int &b, vector<int> &g, vector<int> &s, vector<int> &w, vector<int> &t){
    ll sum_w = 0, sum_g = 0, sum_s = 0;

    for(int i = 0; i < n; i++){
        ll cnt = m / (t[i] * 2); // 왕복
        if(m % (t[i] * 2) >= t[i]) cnt++; // 편도 한 번 더 가능

        ll max_w = min((ll)cnt * w[i], (ll)g[i] + s[i]);
        sum_w += max_w;
        sum_g += min((ll)max_w, (ll)g[i]);
        sum_s += min((ll)max_w, (ll)s[i]);
    }
    return (sum_w >= a + b && sum_g >= a && sum_s >= b);
}
long long solution(int a, int b, vector<int> g, vector<int> s, vector<int> w, vector<int> t) {
    n = g.size();

    ll st = 0, en = 4e14, m = 0;
    while(st < en){
        m = (st+en)/2;
        if(chk(m, a, b, g, s, w, t)) en = m;
        else st = m + 1;
    }
    return en;
}