[ 프로그래머스 [ 월간코드챌린지 ] 금과 은 운반하기 ] (C++)

프로그래머스의 금과 은 운반하기(월간코드챌린지) 문제이다.

 

[ 문제풀이 ]

새로운 도시를 건설하기 위해서 주어진 금과 은의 양이 필요할 때, 이 금과 은을 전달할 수 있는 가장 빠른시간을 구해야 하는 문제이다. 문제에 접근하는 방법부터 구체적인 풀이방법까지 순차적으로 이야기해보자.

 

#1. 접근방법

이 문제를 있는 그대로, 금과 은을 전달할 수 있는 가장 빠른 시간을 구해보는 것이 아니라 반대로 한번 접근을 해보자.

즉, "시간을 미리 정해놓고 그 시간 내로 필요한 금과 은을 모두 운반할 수 있을까?" 라는 관점에서 접근을 해보는 것이다.

다시 말해서, "시간"을 기준으로 '이분탐색'을 통해서 문제에 접근을 해보는 것이다.

왜 이렇게 접근 방법을 바꿔서 접근을 해봐야할까 ?? 그냥 1초부터 시작해서 최악의 경우 걸리는 최대 시간까지 탐색을 하나하나 다 해보면서 문제를 진행해보면 안될까 ?? 안될 건 없다. 당연히 정답은 나올 것이다. 하지만, 이렇게 하게 되면 정답은 나올 수 있더라도 시간초과에 걸리게 될 것이다. 왜냐하면 너무 나도 많은 탐색을 해봐야 하기 때문이다.

여기서 말하는 "너무나도 많은 탐색" 이라는 값이 어느정도 되는지는 아래쪽으로 구체적으로 이야기를 해보자.

즉 ! 그냥 단순한 탐색으로는 너무 많은 시간이 걸리기 때문에 위에서 말한것과 같이 문제를 역으로 생각을 해보는 것이다.

우리는 지금부터 "시간을 정해놓고, 그 시간내에 필요한 금과 은을 모두 운반할 수 있는지?" 로 문제에 접근을 해 나갈 것이다.

이 과정에서 '이분탐색'을 이용할 것이다.

 

#2. 초기값 설정

이분탐색에 대해서 간단하게 이야기를 해보면, 발생할 수 있는 가장 작은 값과 가장 큰 값, 2개의 값을 시작으로 이 두 개의 값에 중간값을 구해서 탐색이 가능한지를 판단해 나가는 탐색법이다.

이 문제에서 우리는 '시간'을 설정을 해줘야 하는데, 발생할 수 있는 가장 작은 시간은 1초가 될 것이다. 그런데, 가장 큰 값은 얼마가 될까 ?? 위에서 이야기했던 "너무나도 많은 탐색" 에 걸리는 시간을 지금부터 구해보자.

아무래도, 가장 많은 시간이 걸린다는 것은 최악의 경우를 말하는 것이고 이 문제에서 최악의 경우를 대충 말로 써보면 이와 같은 상황일 것이다.

"한번 갈 때 마다 옮길 수 있는 광물의 양은 '1'밖에 안되는데, 한번 움직일 때 마다 걸리는 시간은 걸리는 시간의 최댓값인 10^5만큼 걸린다. 즉, 한번에 옮길 수 있는 광물의 양은 너무나도 적은데 한번 옮길 때 마다 움직이는 시간은 너무나도 많이 걸리는 상황인 것이다. 여기에 더해져 옮겨야할 금의 양과 은의 양 또한 10^9으로 최댓값으로 설정되어 있는 경우" 가 아마도 이 문제에서 발생할 수 있는 최악의 경우일 거라 생각한다.

그럼 구체적인 수치로 위의 내용을 다시한번 적어보자.

- 옮겨야 할 금의 양 = 10^9

- 옮겨야 할 은의 양 = 10^9

- 한번에 옮길 수 있는 양 = 1

- 한번 움직이는데 걸리는 시간 = 10^5

다 옮기는데 걸리는 시간은 ??? 어떻게 계산을 해야 할지 감이 안잡힌다.. 그럼 매우 쉬운 값들을 통해서 한번 계산을 해보자.

 

- 옮겨야 할 광물의 총 양(금의양 + 은의양) = 10

- 한번에 옮길 수 있는 양 = 1

- 한번 움직이는데 걸리는 시간 = 10

위의 경우를 한번 계산해보자.

먼저, 계산을 하기 전에 한 가지 알고 가야 할 사실이 하나 있다. 바로, "트럭은 초기에 금과 은이 존재하는 도시에 존재한다" 라는 것이다. 즉 ! 가장 초기 상태에서 트럭은 금과 은을 가지러 가기 위해서 도시로 움직이지 않아도 된다는 것이다. 왜냐하면 이미 그 도시에 정차해있기 때문이다. 그럼, 우리는 트럭이 광물을 가지고 도시로 오는 시간을 계산할 것이니까, 간편하게 '왕복'의 개념으로 계산하기 위해서 이미 한번 금과 은을 옮겨서 새 도시에 트럭이 정차해 있다고 가정을 해보고 진행해보자.

그럼, 트럭이 자신이 있던 원래 도시에서 새 도시로 금과 은을 한번 옮겼으면, 우리가 옮겨야 할 광물의 총 양은 10 - 1 = 9 가 될 것이다. 한번 옮겼기 때문이다. 그리고 이미 걸린 시간 = 10초가 될 것이다. 한번 움직였기 때문이다.

이제부터는 트럭이 한번 광물을 신 도시로 가지고 오는데 걸리는 시간은 20이 될 것이다. 왜냐하면, 현재 트럭의 위치는 신도시에 있고 이 위치에서 광물을 가지러 도시로 들어가는데 10초가 걸리고, 그 광물을 가지고 신 도시로 옮기는데 10초가 걸리므로, 트럭이 한번 광물을 가지고 오는데 걸리는 시간은 20초가 될 것이다.

그럼, 여기까지의 상황에서 우리가 구해야 할 것에 대해서 다시한번 이야기해보자.

"옮겨야 할 광물의 총 양이 '9'이고, 한번에 '1'만큼 옮길 수 있고, 트럭이 광물을 가져오는데 20초가 걸린다면 필요한 광물을 모두 옮기는데 걸리는 시간은 ?"

아마, 20 * (9 / 1) = 180 이라고 계산이 될 것이다.  중간에 '1'만큼 옮길 수 있다는 것 때문에 계산이 조금 너무 단순해 보일 수 있으니, 이렇게 바꿔보자.

- 옮겨야 할 광물의 총 양 = 13

- 한번에 옮길 수 있는 양 = 3

- 한번 움직이는데 걸리는 시간 = 10

마찬가지로 트럭이 한번 움직였다고 가정하면....

- 옮겨야 할 광물의 총 양 = 10

- 한번에 옮길 수 있는 양 = 3

- 한번 움직이는데 걸리는 시간 = 10

- 현재까지 걸린시간 = 10

이 될 것이다. 마찬가지로, 한번 움직이는데 걸리는 시간이 10이므로, 트럭이 광물을 가지고 왔다갔다 하는데 걸리는 시간은 20초가 될 것이다.

그럼, 필요한 광물을 모두 옮기는데 걸리는 시간은 20 * (10 / 3) 으로 계산을 하려고 봤더니, '3'씩 3번을 옮기게 되면 광물이 1이 남게 된다. 그래서 한번 더 움직이게 되므로, 20 * (10 / 3) + 20 + 10 이 될 것이다.

20 * (10 / 3) 만큼 옮긴 후에, 남은 '1'의 광물을 위해서 한번 더 움직여야 하므로 +20이 붙을 것이고, 가장 처음에 도시에서 신도시로 광물을 옮긴시간이 더해져야 하므로 +10이 붙게 될 것이기 떄문이다. 물론, 여기서 필요한 광물의 양이 한번에 옮기는 양으로 나누어 떨어지냐 아니냐에 따라서 또 식이 조금 달라지기는 한다. 하지만 그냥 넘어가자. 위의 예시의 정확한 시간이 중요한 것은 아니기 때문이다. 우리는 더 큰 값을 위해서 이 작은 예시들을 진행해 봤을 뿐이다.

작은 예시들을 통해서 구한 결론을 수식화 시켜보면 다음과 같다.

- 필요한 광물의 전체(금 + 은) 양 = A
- 한번에 옮길 수 있는 양 = B
- 한번 움직이는데 걸리는 시간 = C
[ 필요한 광물을 모두 옮기는데 필요한 시간 ]
약 : (C * 2) * (A / B) + C

위와 같이 대충 계산이 될 것이다. 그럼 다시 본문으로 돌아와보자.

- 옮겨야 할 금의 양 = 10^9

- 옮겨야 할 은의 양 = 10^9

- 한번에 옮길 수 있는 양 = 1

- 한번 움직이는데 걸리는 시간 = 10^5

이라고 이야기를 했는데, 간단하게 '옮겨야 할 광물의 총 양' 을 (2 * 10^9) 이라고 생각하고 계산해보자.

처음에 트럭이 신 도시로 광물을 가지고 나오니까 걸린 시간 = 10^5.

그리고, 1만큼 옮겼으니까 (2 * 10^9 - 1) 만큼의 광물만 옮기면 되는데, 2 * 10^9 이라는 값에 비해서 '1'은 매우 작은 숫자이기 때문에 그냥 계산하지 말자. 위의 수식에 그대로 대입을 해보면....

(10^5 * 2) * ((2 * 10^9) / 1) + 10^5 이 될 것이다. 정리해보면, 4 * 10^14 + 10^5 정도가 된다.

즉, 이분탐색에서 초기값으로 설정할 수 있는 'End'의 값은 (4 * 10^14 + 10^5) 이 된다는 것이다.

그래서 위와 같이 설정을 해줘도 되는데, 본인이 해보니까 10^14 * 3 으로만 하더라도 pass가 되는 것으로 확인되었다..

 

#3. 이분탐색

이제 실제로 주어진 시간 내에 금과 은을 모두 옮길 수 있는지를 판단해보자.

탐색을 하는 과정을 어떻게 진행할 지에 대해서 이야기를 해보자.

1. 트럭은 움직이는데 걸리는 시간은 '편도'의 시간이 주어진다. 즉 ! 광물을 가지고 오는데 걸리는 시간은 주어진

   시간의 * 2가  된다. 이 값을 이용해서 우리는 주어진 시간 내에 광물을 얼마만큼 옮길 수 있는지를 계산할 수 있

   다.

    ex) 트럭의 편도 시간 : 2초, 주어진 시간 : 11초라면, 우리는 이 시간동안 트럭이 총 2번 움직일 수 있다는 것을 알 수 있다.

          왕복 시간이 '4초'가 걸리게 되고, 11초 동안 2번 왔다갔다 할 수 있기 때문이다.

          (밑에서 이 예시를 한번 더 사용할 것입니다. 이 예시를 기억해 주세요.)

    트럭이 한번에 'w'만큼의 광물을 옮길 수 있다면, 우리는 2 * w 만큼의 광물을 주어진 시간 내에 옮길 수 있다는 것을 의미

    한다. 즉, 트럭이 움직이는데 걸리는 시간을 통해서 우리는 주어진 시간 내에 얼마만큼의 광물을 옮길 수 있는지 계산할 수 있다

2. 우리는 3가지 값을 통해서 주어진 시간 내에 광물을 모두 옮길 수 있는지 판단할 것이다.

     1. 주어진 시간 내에 옮길 수 있는 금의 양

     2. 주어진 시간 내에 옮길 수 있는 은의 양

     3. 주어진 시간 내에 옮길 수 있는 전체 광물의 양

여기서, 1번과 2번은 당연히 체크를 해 봐야 할 것이다. 주어진 시간 내에 옮길 수 있는 금의 양이 a이상읹, 그리고 주어진 시간 내에 옮길 수 있는 은의 양이 b이상인지를 판단해봐야 하기 때문이다. 만약, 그 시간 내로 다 옮길 수 없다면 시간이 부족하다는 것을 의미하므로, 시간을 더 늘려줘야 할 것이다. 그런데 여기서 3번판단문, "주어진 시간 내에 옮길 수 있는 전체 광물의 양" 은 왜필요한 것일까 ??? 아래의 상황을 보면서 한번 이야기를 해보자.

위와 같은 상황이라고 가정해보자. 4개의 도시가 있고 그 도시들에 있는 금과 은의 양이 위와 같이 주어졌다.

우리는 신도시를 건설하는데 총 금이 40, 은이 40이 필요하다고 가정해보자.

그리고, 주어진 X초 내에 트럭이 옮길 수 있는 광물의 양이 10으로 1 ~ 4번 트럭 모두 동일하다고 가정해보자.

그럼 여기서 이렇게 계산을 할 수가 있을 것이다.

1 ~ 4 번 트럭들이 모두 금을 운반한다면, 총 40의 금을 운반할 수 있을 것이고, 1 ~ 4번 트럭들이 모두 은을 운반한다면, 총 40의 은을 운반할 수 있을 거라는 것을 알 수 있다.

그렇다고 해서 우리가 금도 40을 운반할 수 있고, 은도 40을 운반할 수 있으므로 신도시에 필요한 금과 은을 모두 주어진 X초 내에 운반할 수 있다 라고 말을 할 수 있을까 ?? 딱봐도 그렇게 말을 할 수 없다는 것을 알 수 있다.

딱 봐도 그럴 수 없다는 것을 우리는 알 수 있지만 이게 왜 이렇게 되는 것일까에 대해서 생각을 해보자.

각각의 트럭들이 주어진 시간 내에 옮길 수 있는 광물의 양이 10이기 떄문에 1 ~ 4번 트럭들이 옮길 수 있는 광물의 총 합은 40이 될 것이다. 그런데, 신도시를 건설하는데 필요한 광물의 양은 금 40 + 은 40 으로 80이 필요하게 된다.

즉 ! 옮길 수 있는 광물의 총 합이 신도시를 건설하는데 필요한 광물의 총 합보다 더 작기 때문에 주어진 X초 내에는 필요한 모두 광물을 옮길 수 없다고 판단을 할 수 있게 되는 것이다. 우리는 위와 같이 계산을 진행할 것이다.

 

#4. 필요한 데이터

사실 #1과 #2에서 했던 이야기들 중간중간에 숨어있는, 탐색에 필요한 데이터들에 대해서 마지막으로 정리를 해보자.

위에서 했던 이야기들과 중복되는 내용들이 있을 수 있다.

1. 트럭이 한번 움직이는데 걸리는 시간은 '편도' 로 주어진다. 우리는 '왕복'의 값을 구해야 하기 때문에 트럭이

    한번 광물을 가지고 오는데는 주어진 '편도' 시간 * 2 만큼이 된다.

아까 위에서 기억해놓자고 했던 예시를 한번 다시 가지고 와보자.

ex) 트럭의 편도 시간 : 2초, 주어진 시간 : 11초라면, 우리는 이 시간동안 트럭이 총 2번 움직일 수 있다는 것을 알 수 있다.

      왕복 시간이 '4초'가 걸리게 되고, 11초 동안 2번 왔다갔다 할 수 있기 때문이다.

사실, 위의 예시는 잘못된 예시이다. 위의 예시의 결과로는 11초 동안 트럭이 2번 왔다갔다 할 수 있다고 말을 했고, 결국 광물을

2번만큼만 옮길 수 있는 것처럼 보이지만, 사실은 3번을 옮길 수 있다.

직접 하나하나 다 해보자. 처음에 트럭은 '자신의 도시' 에 있을 것이다. 자신의 도시에서 신도시로 광물을 첫 2초 동안 옮기게 될 것이다. (광물을 옮긴 횟수 = 1번 , 현재 사용한 시간 = 2초)

신도시에서 다시 자신의 도시로 2초를 사용해서 들어갈 것이고, 자신의 도시에서 2초를 사용해서 광물을 가지고 신도시로 올 것이다. (광물을 옮긴 횟수 = 2번 , 현재 사용한 시간 = 6초)

신도시에서 다시 자신의 도시로 2초를 사용해서 들어갈 것이고, 자신의 도시에서 2초를 사용해서 광물을 가지고 신도시로 올 것이다. (광물을 옮긴 횟수 = 3번 , 현재 사용한 시간 = 10초)

여기서 다시 자신의 도시로 돌아가는데 2초를 사용하게 되면 주어진 시간인 11초를 넘어버리기 때문에 더 이상 트럭은 움직일 수 없다.

왜 주어진 시간이 11초이고 광물을 한번 옮기는데 걸리는 시간이 4초인데, 3번의 광물을 옮길 수 있는 것일까 ??

바로, 트럭의 시작점이 자신의 도시이기 때문이다. 처음에 광물을 옮기는 시간은 4초가 아닌 2초만 있으면 되기 때문이다.

즉, 트럭이 4초를 써서 광물을 2번 옮기고, 3초가 남게 되는데 이 3초동안 광물을 한번 더 옮길 수 있다는 것을 의미한다.

 

그럼 다른 예시를 한번 진행해보자. 위와 똑같은 예시인데, 주어진 시간이 11초가 아닌 9초라고 가정해보자.

처음에 트럭은 '자신의 도시'에 있을 것이다. 자신의 도시에서 신도시로 광물을 첫 2초동안 옮기게 될 것이다.

(광물을 옮긴 횟수 = 1번 , 현재 사용한 시간 = 2초)

신도시에서 다시 자신의 도시로 2초를 사용해서 들어갈 것이고, 자신의 도시에서 2초를 사용해서 광물을 가지고 신도시로 올 것이다. (광물을 옮긴 횟수 = 2번, 현재 사용한 시간 = 6초)

신도시에서 다시 자신의 도시로 2초를 사용해서 들어갈 것이고, (현재 사용한 시간 = 8초) 자신의 도시에서 2초를 사용해서 광물을 가지고 신도시로 오는 순간 사용한 시간이 10초가 되어서 시간이 넘어버리기 때문에 이 광물은 옮길 수가 없다.

즉, 트럭이 4초를 써서 광물을 2번 옮기고, 1초가 남게 되는데 이 1초동안 광물을 더이상 옮길 수 없다는 것을 의미한다.

 

그럼 정리를 한번 해보자.

- 주어진 시간 = K

- 트럭이 한번 움직이는데 걸리는 시간 = A

- 트럭이 왕복으로 움직이는데 걸리는 시간 = A * 2 = B

- 트럭이 광물을 옮길 수 있는 횟수 =

  - K % B >= A 라면, 광물을 옮길 수 있는 횟수 = (K / B) + 1

  - 그게 아니라면, 광물을 옮길 수 있는 횟수 = (K / B)

 

2. 옮길 수 있는 광물의 총 량은 트럭이 한번에 옮길 수 있는 광물의 양과 트럭이 광물을 옮길 수 있는 횟수를 통해서

   구할 수가 있다. 트럭이 광물을 A번 옮길 수 있고 트럭이 한번에 옮길 수 있는 광물의 양은 B라면, 이 트럭이 옮길

   수 있는 광물의 총 량은  A * B 가 된다.

 

위의 2가지 데이터들을 통해서 #2의 내용으로 탐색을 진행한다면 정답을 도출할 수가 있다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool Search(int a, int b, vector<int> g, vector<int> s, vector<int> w, vector<int> t, long long Mid)
{
    long long Total_Gold = 0;
    long long Total_Silver = 0;
    long long Total_Mineral = 0;
 
    for (int i = 0; i < g.size(); i++)
    {
        long long Time = t[i];
 
        long long Round_Time = Time * 2;
        long long Move_Cnt = Mid / Round_Time;
        if (Mid % Round_Time >= Time) Move_Cnt++;
        long long Max_Take = w[i] * Move_Cnt;
 
        Total_Gold += min((long long)g[i], Max_Take);
        Total_Silver += min((long long)s[i], Max_Take);
        Total_Mineral += min((long long)g[i] + s[i], Max_Take);
    }
 
    if (Total_Gold >= a && Total_Silver >= b && Total_Mineral >= a + b) return true;
    return false;
}
 
long long solution(int a, int b, vector<int> g, vector<int> s, vector<int> w, vector<int> t)
{
    long long answer = -1;
    long long Start = 0;
    long long End = 10e14 * 3;
    answer = End;
    while (Start <= End)
    {
        long long Mid = (Start + End) / 2;
        if (Search(a, b, g, s, w, t, Mid) == true)
        {
            answer = min(answer, Mid);
            End = Mid - 1;
        }
        else Start = Mid + 1;
    }
 
    return answer;
}