문제

https://programmers.co.kr/learn/courses/30/lessons/42583

나의 코드 (답안참조)

"""
1. 아이디어

2. 시간복잡도

"""

def solution(bridge_length, weight, truck_weights):
    
    time = 0
    
    now_bridge = [0] * bridge_length # 현재 다리의 상황
    now_bridge_sum = sum(now_bridge) # 현재 다리위에 있는 트럭의 무게의 합
    
    while truck_weights:
        
        now_bridge_remove = now_bridge.pop(0)
        if now_bridge_remove > 0: # 다리를 지난 트럭이 존재 할 경우 무게의 합에서 빼준다.
            now_bridge_sum -= now_bridge_remove
        
        # 만약 대기 트럭이 다리위에 올라서도 다리가 견딜 수 있다면 현재 다리위 트럭의 무게의 합을 더해준다.
        if now_bridge_sum + truck_weights[0] <= weight: 
            now_bridge_sum += truck_weights[0]
            now_bridge.append(truck_weights.pop(0))
        else: # 다리가 견딜 수 없다면 다리 위에 0을 추가해준다.
            now_bridge.append(0)
        
        time += 1
            
    time += bridge_length # 반복문이 끝나면 다리 위의 트럭은 다 못건넌 상태이므로 다리 길이 만큼 더해준다.
    
    return time
    

설명

백준에도 똑같은 문제가 있는데 역시 자주보지 않으니 까먹게 된다.

일단 다리 위의 상황을 표현하기 위해 now_bridge라는 변수에 다리 길이 만큼의 리스트를 생성해준다. 그리고 반복문 내에서는 시간이 지남에 따라 변하는 다리 위의 상황을 구현해주면 된다.

첫번째로 다리위의 트럭을 1개 빼는데 만약 이 트럭이 실제 트럭이라면 다리 위 무게의 합에서 뺴주고 실제 트럭이 아니라면 그냥 지나간다.

두번째로 대기 트럭간의 관계에서 만약 대기 트럭의 트럭을 다리 위로 옮겼을때 다리가 하중을 견딜 수 있다면 다리 위의 트럭의 무게의 합을 더해주고 대기 트럭에서 다리 위로 트럭을 옮긴다. 하지만 다리가 하중을 견딜 수 없다면 0이라는 값을 다리 위에 넣어준다.

다시 풀이한 코드

def solution(bridge_length, weight, truck_weights):
    
    bridge = [0] * (bridge_length)
    bridge_weights = 0
    time = 0
    
    while truck_weights:
        
        out_truck = bridge.pop(0)
            
        bridge_weights -= out_truck
        
        if bridge_weights + truck_weights[0] <= weight:
            
            in_truck = truck_weights.pop(0)
            bridge.append(in_truck)
            bridge_weights += in_truck
        
        else:
            bridge.append(0)
    
        time += 1
        
    time += bridge_length
    
    return time
 

다시 안보고 풀었지만 위의 정답과 똑같이 풀었다. (코드 설명은 위의 정답과 같으므로 생략)

참고자료

X