728x90
반응형
https://programmers.co.kr/learn/courses/30/lessons/86053?language=python3
최종 코드
def solution(a, b, g, s, w, t):
answer = 0
left = 0
right = 10**14*4
while left <= right:
mid = (left+right)//2
g_sum, s_sum, total = 0, 0, 0
for gold, silver, weight, time in zip(g, s, w, t):
cnt = mid//(time*2)
if mid % (time*2) >= time: cnt += 1
new_gold = gold if gold <= weight*cnt else weight*cnt
new_silver = silver if silver <= weight*cnt else weight*cnt
g_sum += new_gold
s_sum += new_silver
total += new_gold+new_silver if new_gold+new_silver <= weight*cnt else weight*cnt
if g_sum >= a and s_sum >= b and total >= a+b: break
else:
left = mid + 1
continue
answer = mid
right = mid - 1
return answer
풀이 과정
풀이 시간 1시간 10분
처음에는 그리디 알고리즘을 이용해볼 수 있을까 했는데 다양한 입력에 대한 대응이 어려울 수 있겠다고 판단하게 되었다.
우선 문제는 금 a kg과 은 b kg을 전달할 수 있는 가장 빠른 시간을 구하라고 되어있으며 이때 입력값이 매우 크다.
최악의 경우에는 a = b = 10^9, g = [1], s = [1], w = 1, t = 10^5인 경우를 생각해 볼 수 있다.
그러면 정답은 10^9*10^5*2 + 10^9*(10^5*2-1)이다.
즉, 시간의 범위가 매우 큰데 그 중에서 필요한 금과 은을 전달하는 최소 시간을 구해야하기 때문에 시간에 대한 이분탐색을 적용해 문제를 해결할 수 있었다.
mid 시간동안 운반한 금과 은의 각각의 총량을 구해서 a와 b보다 각각 크다면 right 범위를 조정해주고, 그렇지 않다면 left 범위를 조정해주었다.
이때, 주의해야 할 점은 금과 은을 동시에 운반할 수 있는 w를 잘 고려해야 한다.
따라서, 운반한 금과 은의 총량도 따로 구해주고 a+b 이상인 경우에 필요한 만큼 금과 은을 운반할 수 있다는 것을 처리할 수 있었다.
def solution(a, b, g, s, w, t):
answer = 0
#시간에 대한 이분탐색을 위한 초기값 설정
# 최악의 경우, a = b = 10^9, g = [1], s = [1], w = [1], t = [10^5]라면 10^9*10^5*2 + 10^9*(10^5*2-1)이 소요된다
left = 0
right = 10**14*4
while left <= right:
#총 소요 시간을 mid로 가정
mid = (left+right)//2
#mid 시간동안 운반한 금의 총량, 은의 총량, 금과 은의 총량
g_sum, s_sum, total = 0, 0, 0
for gold, silver, weight, time in zip(g, s, w, t):
#편도 횟수 구하기
cnt = mid//(time*2)
if mid % (time*2) >= time: cnt += 1
#현재 도시에서 운반한 금의 양 구하기
new_gold = gold if gold <= weight*cnt else weight*cnt
#현재 도시에서 운반한 은의 양 구하기
new_silver = silver if silver <= weight*cnt else weight*cnt
#총량 더해주기
g_sum += new_gold
s_sum += new_silver
total += new_gold+new_silver if new_gold+new_silver <= weight*cnt else weight*cnt
#필요한 금과 은을 운반한 경우, for문 탈출
if g_sum >= a and s_sum >= b and total >= a+b: break
#금과 은을 필요한만큼 운반하지 못한 경우, left 값을 조정한다
else:
left = mid + 1
continue
#금과 은을 필요한만큼 운반한 경우, right 값을 조정한다
answer = mid
right = mid - 1
return answer
#시간복잡도 = O(n log2 n), 공간복잡도 = O(n)
728x90
반응형
'코테 노트 > 프로그래머스' 카테고리의 다른 글
Level 3 퍼즐 조각 채우기 Python 3 (0) | 2022.03.15 |
---|---|
Level 3 아이템 줍기 Python 3 (0) | 2022.03.15 |
Level 2 방문 길이 Python 3 (0) | 2022.03.13 |
Level 2 n^2 배열 자르기 Python 3 (0) | 2022.03.11 |
Level 2 모음사전 Python 3 (0) | 2022.03.11 |