문제 주소
https://school.programmers.co.kr/learn/courses/30/lessons/86053
풀이 과정
처음에는 이문제의 풀이의 방향을 잡지 못했다. 도시의 개수를 하나씩 늘려가면서 계산할 까 했지만 너무 복잡하고 시간이 오래걸릴것 같았다. 그렇다고 시간을 늘려가면서 최소 시간을 찾는것 역시 무리일 것 같았다. 그래서 다른사람의 글로부터 약간의 힌트를 얻었다.
parametric search에 대해서 알아야 문제를 풀 수 있다고 해서 이에 대해 알아보았다.
parametric search
parametric search는 특정한 조건을 만족하는 최소값이나 최대값을 찾을 때 사용하는 방법으로, 해당 값(최소나 최대)이 가질 수 있는 최소값과 최댓값을 설정한 후, 이진 탐색으로 범위를 좁혀나가며 값을 찾는 방법이다.
조건 만족 여부로 탐색을 수행해야 하므로, 조건을 만족하는 구간과 그렇지 않은 구간은 연속된 두 구간으로 나뉘어 져야 한다. 즉, 예를 들어 100이 조건을 만족하는 최소값이라고 하면 100 이상의 수는 모두 조건을 만족해야 한다. 이경우에는 100 미만이면 조건을 만족하지 않고 이상이면 만족하게 되는것이다.
이 방법을 사용할때의 관건은 조건 만족 여부를 계산하는 것인데, 이 문제의 경우 최악의 경우에 다소 연산 시행횟수가 많아보여서 걱정이 됬지만 일단 작성했다.
상세 풀이
먼저 각 도시에 대한 정보를 객체에 저장했다.
parametric search로 찾을 값은 금, 은을 모두 수송할 수 있는 시간의 최소값이다. 따라서 조건은 해당 시간 안에 금, 은을 모두 수송할 수 있는지 여부이다.
각 도시에서 새 도시로 가는데 걸리는 시간을 1시간이라고 하면, 1시간에 1번 수송, 3시간에 2번 수송, 5시간에 3번 수송, ..., 2n - 1시간에 n번 수송이 가능하다. 따라서 시간에 1을 더하고 2로 나누면 수송 가능 횟수가 나온다. 만약 도시로 가는데 걸리는 시간이 m시간이면 시간을 m으로 나눈 후, 위 로직을 적용하면 된다.
수송 횟수에 한번 수송할 때 가져올 수 있는 무게를 곱하면 총 가져올수 있는 광물 양이 된다. 이를 이용해 도시마다 특정 시간동안 가져올 수 있는 광물의 최대무게, 금의 최대무게, 은의 최대무게를 반환한다.(getMaxGS())
각 도시마다 위 값을 계산해서 모두 더하면 총 가져올 수 있는 광물의 최대무게, 금의 최대무게, 은의 최대무게가 된다. 이때 a + b의 값이 광물의 최대보다 크거나 같고, a가 금보다 크거나 같고, b가 은보다 크거나 같으면 조건을 만족한다. 만약 첫번째 조건을 만족하지 않는다면 각각 가져오는것은 가능해도 금, 은 둘다 모두 가져오는 것은 불가능할 수도 있다.
만약 해당시간에 금, 은을 모두 가져올 수 있으면 시간을 줄이고, 없다면 늘린다. 이 과정을 반복해서 최소값을 찾으면 된다.
최종 코드
class Solution {
City[] cities;
public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) {
cities = new City[g.length];
for(int i = 0; i < g.length; i++){
cities[i] = new City(g[i], s[i], w[i], t[i]);
}
return recursion(a, b, 0L, 400_0000_0000_0001L);
}
private long recursion(int a, int b, long min, long max){
if(min == max) return min;
long mid = (min + max) / 2;
int maxT = 0;
int maxG = 0;
int maxS = 0;
for(int i = 0; i < cities.length; i++){
int[] result = cities[i].getMaxGS(mid);
maxT += result[0];
maxG += result[1];
maxS += result[2];
}
if(maxT >= a + b && maxG >= a && maxS >= b) return recursion(a, b, min, mid);
return recursion(a, b, mid + 1, max);
}
private class City{
int gold;
int silver;
int weight;
int time;
public City(int gold, int silver, int weight, int time){
this.gold = gold;
this.silver = silver;
this.weight = weight;
this.time = time;
}
public int[] getMaxGS(long time){
int[] result = new int[3];
long count = (time / this.time + 1) / 2;
int max = (count * weight > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)(count * weight);
result[0] = Math.min(max, gold + silver);
result[1] = Math.min(max, gold);
result[2] = Math.min(max, silver);
return result;
}
}
}