23.04.10 파이썬 코딩 퀴즈#212 금과 은 운반하기(프로그래머스 스쿨)

이번 문제는 금과 은 운반하기 문제이다.

문제 설명은 굉장히 심플하다. 우선 도시를 건설할 때 필요한 금과 은 수량이 a , b로 전달 된다.

각 도시는 index 로 구분하며, 금(g)과 은(s) 그리고 트럭 한대가 주어진다.

트럭은 오로지 해당 도시와 건설 장소만 오갈 수 있으며, 이때 걸리는 편도 시간은 t, 그리고 최대 운반 수량은 w 에 전달된다. 모든 트럭은 왕복 가능하며, 연료는 무제한이다.

전달받은 6개의 매개변수를 확인하여 새로운 도시를 건설하기 위한 가장 빠른 시간을 구해 return 해야 한다.

 

특별한 건 없어 보인다. 

 

입출력 예 1번의 경우 금 또는 은을 보유한 도시의 수는 len(g) 또는 len(s)와 같다. 입출력 예 2 번에 나오듯이 만약 해당 도시 i 에 보유량이 없으면 0으로 전달된다. 즉 하나의 리스트의 길이만 확인해도 문제 없다.

a, b 금과 은의 요구량은 각 10 이다. 그리고 도시[0]의 금은 보유량은 각 100 이다. 한번에 최대 7kg 를 운반 가능하기에

1회 : 금 7kg 운반 후 복귀 (10 x 2)

2회 : 은 7kg 운반 후 복귀 (10 x 2)

3회 : 금 3kg + 은 3kg (10) 후 도시 완성

이므로 총 50시간이 소요된다.

 

입출력 예 2번을 살펴보면

도시 건설에 필요한 금은 90, 은은 500kg 이다.

각 마을의 금은 보유량을 묶어서 보면 1번 마을은 (70,0), 2번 마을(70,0) 3번마을 (0,500)이다. 이며 각 마을의 트럭의 최대 적재량은 100, 100, 2 이다.

먼저 1번 마을에서 금을 70kg 전달한다. 4시간 소요

동시에 2번 마을에서 금을 20kg 전달한다. 8시간 소요

그리고 3번 마을에서는 500은 2kg 씩 나눠서 전달하게 되는데, 이때 왕복으로 시간을 계산하므로 249번 왕복 후 (498 시간) 한 번만 편도로 운반하면 도시는 완공된다.

따라서 총 걸린 시간은 499시간이 된다.

 

전형적인 이분탐색 문제이다.

다만 정확하게 어떤 수치를 가지로 탐색을 진행해야 할지 처음에는 감이 안오는 문제이다.

먼저 answer은 최대값으로 설정해 둔다.

그리고 이분탐색을 위한 start ,end 변수를 정해주는데, 여기서 end는 문제에서 제공하는 (최대 도시의 수 )* (각 광물의 최대 수량) * 왕복 이다. 금과 은이 주어지기 때문에 최종적으로 4배를 설정하였다.

 

이제 while문을 통해서 start <= end 조건을 가지고 반복문을 돌게 된다.

반복문을 돌때마다 갱신해줘야 하는 값은 mid (start + end 의 절반) 와 현재 전달 되는 gold, silver, 그리고 광물의 총량이다.

광물의 총량은 한번에 배송 가능한 무게를 초과하지 않아야 하기에 필요하다.

이제 반복문을 돌면서 현재 도시에서 보유하고 있는 금, 은, 배달가능량, 시간 을 뽑아낸다.

여기서 cnt 는 현재 주어진 시간 mid 동안 왕복 가능한 횟수이다.

즉 mid 로 90시간이 주어졌고, 현재 마을에서 트럭으로 가는데 10시간 걸린다면, 왕복으로 계산하면 20시간이고 총 4회 왕복 가능하다.

만약 90시간을 왕복시간 20시간으로 나눈 나머지가 배송시간 10시간보다 크거나 같다면 이는 편도로 한번 전달이 가능함을 의미한다 .따라서 이 경우 따로 cnt 값을 1 회 증가시켜준다.

 

이제 각 마을에서 전달 가능한 금과 은을 계산해야 한다.

계산법을 살펴보면, 먼저 왕복 횟수 * 무게를 계산한다. 즉 mid 시간만큼 얼마만큼의 금을 전달 가능한지 확인해야 한다.

만약 보유량을 초과한 경우라면 현재 보유한 금 만큼 전달한다. 은도 동일하다.

그리고 이제 전체 무게를 확인해야 한다.

이때에도 왕복 횟수만큼 전달가능한 수량과 현재 금,은 보유량을 비교한다.

만약 충분히 보유하지 못한 경우라면 total 은 현재 금,은 보유량의 합이 되며, 충분히 보유한 경우라면 mid시간만큼 전달 가능한 수량이 된다.

모든 마을에서 위 계산을 거쳐 gold , silver, total 값이 정해진다면, 이제 요구량 a,b와 비교해야 한다.

gold, silver, total 값이 모두 기준값을 넘어선 경우라면 end값을 감소시켜 준다. 그리고 answer을 갱신한다.

만약 부족한 경우라면 start 값을 증가시켜 주면 된다.