728x90
https://school.programmers.co.kr/learn/courses/30/lessons/86053
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
분석
최솟값(0)과 최댓값(가장 오래 걸리는 도시 트럭으로 금과 은 전체 운반) 사이를 이분 탐색을 통해 최적값 찾아내기
a : 필요한 금의 무게
b : 필요한 은의 무게
g : 각 도시의 금의 양
s : 각 도시의 은의 양
w : 각 도시의 트럭이 운반할 수 있는 최대 무게
t : 도시에서 이동하는 편도 시간
a b g s w t result 90 50 [70, 70, 0] [0, 0, 500] [100, 100, 2] [4, 8, 1] 499
l r time gold sirver weight 0 9440 4720 140 500 640 0 4720 2360 140 500 640 0 2360 1180 140 500 640 0 1180 590 140 500 640 0 590 295 140 500 640 296 590 443 140 500 584 444 590 517 140 500 584 444 517 480 140 480 620 481 517 499 140 500 640 481 499 490 140 490 630 496 499 497 140 498 638 498 499 498 140 498 636
2023.05.25 - [BOJ/Search] - [1654] 랜선 자르기(이분탐색, 결정 알고리즘)
[1654] 랜선 자르기(이분탐색, 결정 알고리즘)
1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고
karla.tistory.com
풀이
from math import ceil, floor
def solution(a, b, g, s, w, t):
answer = -1
def count(time):
gold=0
silver=0
weight=0
for i in range(len(g)):
tmp=floor(time/t[i])
deliver=tmp//2+tmp%2
gold+=min(g[i], w[i]*deliver) # 가지고 있는 골드, 트럭 용량 작은 값
silver+=min(s[i], w[i]*deliver) # 가지고 있는 실버, 트럭 용량 작은 값
weight+=min(g[i]+s[i], w[i]*deliver)
if gold>=a and silver>=b and weight>=a+b:
return True
else:
return False
l=0
r=(a+b)*max(t)*2
while l<r:
print(l,r)
mid=(l+r)//2
if count(mid):
answer=mid
r=mid
else:
l=mid+1
return answer
728x90