[프로그래머스][python]금과 은 운반하기

문제

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

소스코드

    def solution(a, b, g, s, w, t):
        L = 0
        R = 1 * 10**9 * 10**5 * 2 * 2 # 최소의 무게 1을 10**9번 옮기는 경우 이때 1번 옮기는데 시간이 10**5 시간 걸리고 왕복이고 금/은 둘다 해야한다.
        town = len(g) # 모든 마을을 순회하면서 옮길 수 있는 금과 은의 무게를 체크해야함
        while L <= R:
            T = (L+R)//2 # 특정 시간 내에 광물을 이동할 수 있을지가 우리의 target값
            TOTAL = 0
            G = 0
            S = 0
            for i in range(town):
                # weight 구하는 방법 1
                # weight = w[i] + ((T - t[i]) // (t[i] * 2)) * w[i]
                
                # weight 구하는 방법 2
                # cnt 구하는 방법 1
                cnt = T // (t[i]*2) # 왕복으로 움직일 수 있는 횟수
                if T % (t[i]*2) >= t[i]: # 편도로 움직일 수 있는 횟수, 왕복으로 움직일 수 있는 횟수를 제외하고도 편도로 갈 수 있을 여유가 있으면 편도로 간다.
                    cnt +=1
                # cnt 구하는 방법 2
                # cnt = 1 + (T-t[i] // t[i]*2 ) # 무조건 편도로 한번 가고 + 전체 시간에서 편도로 가는 시간을 제외하고 왕복으로 갈 수 있는 시간 체크
                weight = w[i] * cnt # 한 도시에서 가지고 갈 수 있는 무게는 "트럭 최대 용량 * 이동 횟수"
                
                G += min(weight,g[i]) # 한 도시에서 가지고 갈 수 있는 금의 최대 무게는 "한 도시에서 가져갈 수 있는 최대값" 괴 " 금의 최댓값중 작은 값
                                      # 금의 최댓값보다 더 큰값을 가져갈 수 없음
                S += min(weight,s[i]) # 은도 동일 근데 모든 도시를 돌아야하니까 누적해줌
                TOTAL += min(weight,g[i]+s[i]) # 금과 은을 함께 가져가는 경우도 체크 weight만 체크하면 안되는 이유는 한 도시에서 가져갈 수 있는 최댓값보다
                                               # 금 + 은 값이 작으면 금 + 은 값이 가져갈 수 있는 최댓값
            if G >= a and S >= b and TOTAL >= a+b: # 모든 도시를 돌았을 때 조건을 충족하면
                R = T -1  #시간을 조금 줄여서 할 수 있는지 확인
            else:
                L = T + 1

        return L #조건을 만족하는 최솟값 L = R이 되는 값

설명

이분탐색 문제이고 파라메트릭 서치 문제이다.

우리가 구해야하는 값은 "광물을 모두 옮길 수 있는 최소 시간" 이다. 

 

그러면 우리는 특정 시간 T를 정해놓고 "광물을 옮길 수 있어? 광물을 옮길 수 없어?" 를 체크해주면 된다.

이렇게 파라메트릭 서치를 해주면 계속 False가 나오다가 어느 순간 True가 나올 것이다. -> [False, False, .... , True, True, .. True]

그리고 특정 시간 이후엔 계속 True가 나올텐데 이때 이분탐색을 이용해서 최소 시간을 구해주면 된다.

 

문제 풀이 알고리즘을 설명하면 다음과 같다.

1.범위 설정

최소값 L 값은 광물을 옮길 수 있는 최소 시간이다. -> 1

최댓값 R 은 최악의 경우로 광물을 옮길 수 있는 최대 시간이다.

가장 적은 무게(1)를 가장 많이 이동(10**9)하고 한번 이동할 때 가장 오랜 시간(10**5)을 이동하면 된다. 그리고 왕복(2)이고 금과 은 둘다(2)를 생각해주면 된다. -> 1*(10**9)*(10**5)*2*2

 

2.이분탐색

이분탐색을 이용해서 최소시간을 구해준다.

이분탐색을 할 때 전체 도시를 다 돌면서 구할 수 있는 광물의 무게를 체크한 후 이분탐색이 끝나면 그동안 구한 광물을 모두 체크해서 조건을 만족했는지 확인해야한다. 

 

각 도시를 돌면서 확인해야하는 값은 3가지가 있다.

1. 도시에서 들고 올 수 있는 금의 양 (G)
2. 도시에서 들고 올 수 있는 은의 양 (S)
3. 도시에서 들고 올 수 있는 금+은의 양 (TOTAL) 

이 세가지를 각 도시마다 누적해서 계산해줘야 a와 b를 만족했는지 알 수 있다. (자세한 풀이는 주석 참고)

 

2-1. 먼저 도시에서 주어진 시간동안 한 트럭이 최대 얼마 만큼의 광물을 가져올 수 있는지 체크한다. 

(이건 내가 너무 헷갈렸어서 자세히 기록)

왕복으로 갔을 때 들고 가는 광물양 + 편도로 갔을 때 들고 가는 광물 양 (자세한 풀이법은 주석)

 

방법 1 : 왕복 카운트와 편도 카운트를 모두 계산하기

cnt = T // (t[i]*2)
if T % (t[i]*2) >= t[i]: 
	cnt +=1
    
weight = w[i] * cnt

• 전체 시간에서 왕복 시간을 나누면 왕복으로 했을 때 몇번 갈 수 있는 지 알 수 있다.
• 전체 시간에서 왕복 시간을 나누고 나머지가 편도 시간보다 크면 편도로 한번 갈 수 있음을 의미한다 왕복 시간보다 무조건 작으니까 편도로 한번만 갈 수 있다.

방법 2 : 방법 1을 한문장으로 축약

cnt = 1 + (T-t[i] // t[i]*2 )
weight = w[i] * cnt

• 무조건 편도로 가고 
• 전체 시간에서 편도로 한번 간 시간 뺀 총 시간에서 왕복 시간으로 나누면 편도로 간 거 제외하고 왕복으로 몇번 갔는지 알 수 있다. 

방법 3 : 바로 무게를 체크하는 방법 : 시간을 그냥 바로 무게로 치환

weight = w[i] + ((T - t[i]) // (t[i] * 2)) * w[i]

 

2-2. 금과 은과 전체 총량을 비교 한다.

 

3. 각 도시를 돌면서 누적된 광물이 문제의 조건을 만족하는지 확인한다.

만족한다면 범위를 줄여보자. R = T -1 

만족하지 않는다면 시간을 조금 더 줘서 광물을 다시 모아보자 L =  T + 1

 

후기

너무 어려웠다.. 

문제 이해 자체를 스터디원들과 토의하면서 이해했다.

풀고나니 이분탐색 + 파라메트릭스 문제이고 단순한 로직이지만 그 안에 코딩하는 과정에서 많은 생각을 필요로 했다.