[python/プログラマー/レベル2]ブリッジトラック


ブリッジトラック
問題の説明
何台ものトラックが川にまたがる橋を所定の順序で渡りたいと思っている.すべてのトラックが橋を渡るのに少なくとも数秒かかります.橋の上で、トラックは最大bridge lengthロッドに乗ることができ、橋は重量より低い重量に耐えることができる.しかし、完全に橋を上がっていないトラックの重さは無視される.
例えば、2台のトラックに乗ることができ、10キロの重量に耐えられる橋があります.重量[7,4,5,6]kgのトラックは最短時間で順番に橋を渡りますので、次のように橋を渡ります.
タイムブリッジを通るトラック待ちトラック0[][7,4,5,6]1~2[][7][4,5,6]3[7][4][4][5][4,5][6][7]6~7[7][4,5][6][6][8][7,4,5,6][7][7][7][7,4,6][6][8][7,4,5,6][][7,4,5][7][7][7][7][7][7][7][7][4,5][][][7][7][7][4,5][7][7
そのため、すべてのトラックは少なくとも8秒で橋を渡ることができます.
solution関数のパラメータには、ブリッジに上がることができるトラックの数bridge length、足が受ける重量、トラック1台当たりの重量cart weightsが含まれます.解の関数を完了し、すべてのトラックが橋を渡るのに少なくとも数秒かかります.
せいげんじょうけん
bridge lengthは1または10000未満です.
Weightは1以上10000以下です.
cart weightsの長さは1または10000以下です.
すべてのトラックの重量は1以上の重量以下です.
I/O例
bridge_lengthweighttruck_weightsreturn210[7,4,5,6]100100[10]101100100[10,10,10,10,10,10,10,10,10,10]110
に答える
この問題はトラックが1台1台運転していることを知らなければならない.(問題があって黙っていたので、少し苦労しました)
問題の説明例を下表のように整理し直します.

トラックが1台1台進み、橋の長さのようです!
例)bridge length=100,weight=100,cart weight=[10]
上の例で説明すると、「最大100キロの重さに耐えられる」「長さ100の橋」「10キロのトラックが1台通るので、少なくとも数秒はかかる」.
答えが101秒だった理由は
10キロのトラックが100フィートの橋を渡り、1秒に1回移動するので、橋から突き当りまで100秒かかります.そして橋を出るのに1秒かかり、100秒+1秒=>101秒が最短時間です.
試行錯誤のケースが続いています...質問で空き地をゼロトラックにしたいというヒントをもらいましたが….ㄳㄳ
_
「トラックでは登れない橋の空間を0で埋めろ!」
これがポイント
例えば、長さ5の橋が最大100キロの重量に耐えられると仮定すると、トラックは100キロ、60キロ、40キロ増加する.
0秒-脚=[0,0,0]sum(脚)=0 kg
1秒-脚=[0,0,0100].sum(脚)=100 kg
せいぜい100キロしか上がらないし、2秒で60キロ上がると100キロを超えるので、100キロが橋から落ちるまで待たなければなりません.
2秒-脚=[0,0100,0]sum(脚)=100 kg
3秒-脚=[0100,0]sum(脚)=100 kg
4秒-脚=[0100,0]sum(脚)=100 kg
5秒-脚=[100,0,0]sum(脚)=100 kg
6秒で100が落ち、sum(足)=0なので、60キロのトラックに乗ることができます.
(後ろの空間が0の場合、ブリッジの長さをbridge lengthに維持し続けることができます.)
6秒-脚=[0,0,0,60]sum(脚)=60 kg
7秒以内でsum(脚)+40 kg=100 kgなので40 kgアップできます.
7秒-脚=[0,0,60,40]sum(脚)=100 kg
待機するトラックがなくなると、つまり最後のトラックが開始されると、最後のトラックが離れる時間を計算するだけです.
最後のトラックが離れる時間はいつも橋の長さと同じです.
よって7秒+5秒=12秒が最短時間!
コード実装
from collections import deque

def solution(bridge_length, weight, truck_weights):
    q = deque([0]*bridge_length)
    
    total_time = 0 # 걸리는 total 시간 
    qSum = 0 # 다리 weight 

    while truck_weights:
        qSum -= q.popleft() # 빠져나온 트럭 무게 제거 
        total_time+=1 # 트럭은 1씩 움직이므로,  while문이 돌아가는 시간 만큼 time 추가

        if (qSum + truck_weights[0])>weight: # 현재 다리 weight + 다음 트럭 무게가 weight를 넘으면
            q.append(0) # 다리에 다음 트럭 올라갈 수 없으므로 0을 추가 

        else:# 다음 트럭이 올라갈 수 있으면 
            next = truck_weights.pop(0) # 다음 트럭 나옴
            qSum += next  # 다음 트럭 무게 추가 
            q.append(next) # 다음 트럭 queue에 추가 
    
    return total_time + len(q) # 다리를 빠져오지 못한 트럭 + total 시간