[Programmers] 금과 은 운반하기

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/86053

프로그래머스

이분 탐색 알고리즘을 통해 풀면 되는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 이분 탐색의 핵심은 탐색의 범위를 지정하는 것이며 저는 시간을 기준으로 범위를 지정했습니다.

1.1 이 문제의 핵심은 최대 시간을 구하는 것인데 극단적인 케이스로 w = 1, t = 1, g = 1e9, 그리고 s = 1e9라고 가정했을 때 최대 시간은 1e5 + (1e5 * 2) * (2 * 1e9 - 1)가 될 것입니다.

1.2. 이유는 즉슨 마지막으로 운반할 때는 왕복을 하지 않아도 되므로 2 * 1e5가 아닌 1e5 시간이 걸리고 나머지 광물( 2 * 1e9 - 1) kg에 대해서는 왕복을 진행해야 하므로 (2 * 1e9 - 1) * (1e5 * 2) 시간이 걸릴 것입니다.

2. 1번에서 범위를 구했으므로 해당 범위를 기반으로 이분 탐색을 진행합니다.

2.1 mid 시간을 기준으로 최대로 옮길 수 있는 금의 양을 gold, 은의 양을 silver, 자원의 양을 weight라고 했을 때 weight가 a + b 이상이고 gold가 a 이상, 그리고 silver가 b 이상일 경우 조건에 부합합니다.

2.2 조건에 부합할 경우 answer를 업데이트하며 더 최적화된 시간을 찾기 위해 최대 시간을 단축시키고 조건에 부합하지 않을 경우 시간을 더 늘려야하므로 최소 시간을 늘려줍니다.

3. 2번을 통해 구한 answer를 반환해줍니다.

 

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~