[프로그래머스][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가지가 있다.
- 도시에서 들고 올 수 있는 금의 양 (G)
- 도시에서 들고 올 수 있는 은의 양 (S)
- 도시에서 들고 올 수 있는 금+은의 양 (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
후기
너무 어려웠다..
문제 이해 자체를 스터디원들과 토의하면서 이해했다.
풀고나니 이분탐색 + 파라메트릭스 문제이고 단순한 로직이지만 그 안에 코딩하는 과정에서 많은 생각을 필요로 했다.