프로그래머스: 금과 은 운반하기⭐⭐⭐
카테고리: Programmers
태그: Algorithm, Blog, C++, Programmers
난이도 ⭐⭐⭐
유형 : 이분탐색, 수학
🧐 문제
문제 설명
어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 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의 모든 수의 합
- 0 ≤
입출력 예
| 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 해야 합니다.
✏️ 풀이
이 문제는 이분탐색을 활용하는 문제이다.
시간이 이분탐색의 주요 Key이며, ‘주어진 시간 안에 필요한 광물들을 모두 운반할 수 있는가?’를 중점으로 봐야한다.
1. 이분탐색
이분탐색을 시작할 때 시간의 범위를 고민해야한다.
start는 1, end는 무엇으로 두어야할까?
end는 ‘문제의 조건 내에서 나올 수 있는 필요한 최대 시간’ 으로 잡으면 된다.
| 최소 | 최대 | |
|---|---|---|
| 무게 | $1$ | $10^2$ |
| 금 | $0$ | $10^9$ |
| 은 | $0$ | $10^9$ |
| 시간 | $1$ | $10^5$ |
여기서 나올수 있는 최대 시간은 다음과 같다.
\[2\times\frac{금+은}{무게}\times시간\] \[= 2\times\frac{2\times10^{9}}{1}\times10^{5}\] \[= 4\times10^{14}\]
그러므로 start는 1, end는 \(4\times10^{14}\)로 잡고 이분탐색을 수행하면 된다.
2. 시간 내 운반 가능한가?
위 풀이에 따라, 아래의 조건을 만족하면 된다.
- \(a <= G_{max}\)
- \(b <= S_{max}\)
- \(a+b <= G_{max} + S_{min} = G_{min} + S_{max}\)
📜 나의 코드
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef unsigned long long ull;
bool canTransportInTime(int a, int b, vector<int>& g, vector<int>& s, vector<int>& w, vector<int>& t, ull time) {
ull total_g = 0;
ull total_s = 0;
ull total_gs = 0;
for(int i=0; i<g.size(); i++) {
// 운반할 수 있는 최대 양
ull total_w = ((ull)(time - t[i]) / (t[i]*2)) * w[i] + w[i];
ull cal_g = min((ull)g[i], total_w);
ull cal_s = min((ull)s[i], total_w);
ull cal_gs = min((ull)(g[i]+s[i]), total_w);
total_g += cal_g;
total_s += cal_s;
total_gs += cal_gs;
}
if(a <= total_g && b <= total_s && a+b <= total_gs) return true;
else return false;
}
ull bs(int a, int b, vector<int>& g, vector<int>& s, vector<int>& w, vector<int>& t) {
ull l = 1;
ull r = 4 * 10e14 + 10e5;
while(l<=r) {
ull mid = (l+r)/2;
if(canTransportInTime(a,b,g,s,w,t,mid)) {
r = mid-1;
} else {
l = mid+1;
}
}
return l;
}
long long solution(int a, int b, vector<int> g, vector<int> s, vector<int> w, vector<int> t) {
long long answer = bs(a,b,g,s,w,t);
return answer;
}
📜 다른 사람의 코드
public class Solution {
public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
long answer = (long) (10e9 * 2 * 10e5 * 2);
int cityLength = g.length;
long start = 0;
long end = (long) (10e9 * 2 * 10e5 * 2);
while (start <= end) {
long mid = (start + end) / 2;
int gold = 0;
int silver = 0;
int add = 0;
for (int i = 0; i < cityLength; i++) {
int nowGold = g[i];
int nowSilver = s[i];
int nowWeight = w[i];
long nowTime = t[i];
long moveCount = mid / (nowTime * 2);
if (mid % (nowTime * 2) >= t[i]) {
moveCount++;
}
gold += Math.min(nowGold, moveCount * nowWeight);
silver += Math.min(nowSilver, moveCount * nowWeight);
add += Math.min(nowGold + nowSilver, moveCount * nowWeight);
}
if (a <= gold && b <= silver && a + b <= add) {
end = mid - 1;
answer = Math.min(mid, answer);
continue;
}
start = mid + 1;
}
return answer;
}
}
🪶 후기
- 이분탐색 보단 수학적인 접근이 어려운 문제였다.
‘주어진 시간 내에 필요한 광물들을 운반할 수 있는지 결정할 수 있어야 한다는 것’은 알고 있었으나, 그것을 어떤 방식으로 풀어나가야 할지에 대해 굉장히 애를 먹었다.
결국, 구글링을 하며 어떤식으로 풀어야할지에 대한 답을 얻었다.
수학적인 감을 더욱 길러야 할 것 같다. - 풀이에 많은 시간이 걸려, 시간을 측정할 수 없었다.
댓글남기기