2023. 3. 17. 03:19ㆍ배움엔 끝이없다/알고리즘
문제
링크 : https://school.programmers.co.kr/learn/courses/30/lessons/86053
요약
신도시를 짓기 위해 금 a만큼과 은 b만큼이 필요하다.
여러 도시에 있는 금과 은의 양, 그 도시의 금을 신도시로 운반하는 트럭의 용량과 속도가 주어진다.
도시들에 있는 금과 은을 모아 신도시를 짓기위해 필요한 최소 시간을 구하는 문제다.
의식의 흐름
일단 처음에 봤을 땐 뭔가 수식으로 풀릴 것 같았다.
하지만 머리를 싸매본 결과 도저히 계산을 할 수 없었다.
이런 문제는 최소/최대 구하기 문제는 이분탐색을 다음으로 생각하게 된다.
이분 탐색을 하기위해 시간 t가 주어졌을 때, 그 시간 동안 운반을 마칠 수 있는지 확인할 수 있어야한다.
이건 충분히 할 수 있을 거라 생각했다.
처음에 수식으로 풀려고 고민하면서 느꼈지만 간단하게는 안되고, 광물을 모을 수 없는 조건을 찾으면 된다.
각 도시별로 t 시간동안 모을 수 있는 최대 금, 최대 은, 최대 금+은을 다 더해서, 그 양이 필요한 양보다 한 항목이라도 적으면 성공할 수 없다.
구현
자료구조
자료구조를 따로 사용하지 않는다.
알고리즘
시간 t가 주어졌을 때, t시간 동안 필요한 광물을 모을 수 없는지 확인하면 된다.
위에 설명한대로 도시별 최대 금, 은, 금+은을 구해 요구량을 한 항목이라도 충족하지 못하는지 확인하면 된다.
여기서 주의할 점은 트럭이 한 번 나를 때는 이동시간 t[i] 만큼 걸리지만, 그 다음부턴 2*(w[i] -1) 만큼 걸린다는 점이다.
다르게 해석하면 총 시간을 t[i]로 나눈 몫을 2로 나누고 올림을 해주면된다.
탐색 범위는 (트럭의 최대 이동시간 10^5) * (금/은의 최대량 10^9) * (금과 은 -> 2) * (왕복 -> 2) = (10&14 * 4) ~ 1이다.
코드
수식으로 풀릴 것 같은데 안풀리고, 주어진 파라미터의 숫자가 매우 크고, 최대/최소를 구하는 문제는
왠만해서 이분탐색으로 풀리는 것 같다.
'''
문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/86053
'''
def solution(a, b, g, s, w, t):
left = 0
right = 10**14 * 4
while left <= right:
mid = (left+right)//2
maxgold = 0
maxsilver = 0
maxtotal = 0
for i in range(len(g)):
moves = (mid // t[i] + 1) // 2
maxgold += min(g[i], w[i] * moves)
maxsilver += min(s[i], w[i] * moves)
maxtotal += min(g[i] + s[i], w[i] * moves)
if (maxgold >= a and maxsilver>=b and maxtotal>=a+b): #mid 시간내에 배달 가능
right = mid - 1
else:
left = mid + 1
return left
'배움엔 끝이없다 > 알고리즘' 카테고리의 다른 글
코딩테스트 스터디 - 프로그래머스 파괴되지 않은 건물(C++) (0) | 2023.11.16 |
---|---|
코딩테스트 스터디 - 프로그래머스 무인도 여행 (python) (0) | 2023.03.08 |
코딩테스트 스터디 - 프로그래머스 스타수열 (python) (0) | 2023.02.28 |
코딩테스트 스터디 - 백준 25406번 : 식사 계획 세우기 (C++) (0) | 2023.01.31 |
코딩테스트 스터디 - 프로그래머스 이모티콘 할인행사 (python) (0) | 2023.01.26 |