반응형
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- DP
- 에라스토테네스의 체
- BFS
- programmers
- 힙
- level0
- 파이썬
- 딕셔너리
- 가상메모리
- 다익스트라
- 브루트포스
- 가상메모리 관리
- BOJ
- dfs
- python
- 다이나믹 프로그래밍
- 수학
- 운영체제
- level2
- 스택
- MYSQL
- 백준
- 그리디
- 구현
- N과M
- level1
- level3
- 코딩테스트
- 프로그래머스
- 재귀
Archives
- Today
- Total
동캄의 코딩도장
백준 13335 [트럭] 파이썬 본문
반응형
https://www.acmicpc.net/problem/13335
생각보다 시간이 오래 걸렸다.
알고리즘은 간단한데.. 구현하는게 생각보다 어려웠다.
#백준 13335 트럭
from collections import deque
n,w,l=map(int,input().split()) # 트럭수, 통과시간, 제한하중
trucks=list(map(int,input().split())) #트럭 배열 저장
trucks=deque(trucks) # 트럭 배열 덱으로 변환
truck_on_brdg=deque([]) # 다리위에 있는 트럭 덱 초기화
ans=0 #정답 (총 시간간)
total_weight=0 # 총 무게
def search():
global ans
global total_weight
i=0
while i<n: #모든 트럭이 통과하지 않았다면
if total_weight+trucks[i]>l: #현재 다리위에 트럭이 있어 다음 트럭이 들어올 수 없을 때
time_left=truck_on_brdg[0][1] #가장 앞에 있는 트럭의 남은 시간만큼 경과 시킴
ans+=time_left
total_weight-=truck_on_brdg[0][0] #가장 앞에 있는 트럭의 무게 만큼 총 무게에서 뺌
truck_on_brdg.popleft() #가자 앞에 있는 트럭은 다리를 통과
for j in range(len(truck_on_brdg)-1,-1,-1): # 가장 앞에 있는 트럭이 다리를 통과하는데 걸리는 시간만큼 다리위의 나머지 트럭들의 남은 시간을 빼줌
truck_on_brdg[j][1]-=time_left
if total_weight+trucks[i]<=l: #만약 트럭이 통과하고 다음(새로운) 트럭이 들어올 수 있다면 추가
truck_on_brdg.append([trucks[i],w])
total_weight+=trucks[i]
i+=1
continue
elif total_weight+trucks[i]<=l: #현재 다리에 다음 트럭이 들어올 수 있다면 추가
if truck_on_brdg:
for j in range(len(truck_on_brdg)-1,-1,-1):
truck_on_brdg[j][1]-=1
if truck_on_brdg[0][1]==0:
total_weight-=truck_on_brdg[0][0]
truck_on_brdg.popleft()
total_weight+=trucks[i]
truck_on_brdg.append([trucks[i],w])
ans+=1
i+=1
search()
if truck_on_brdg: #혹시 다리위에 남은 트럭이 있다면 통과 시킴
while truck_on_brdg:
time_left=truck_on_brdg[0][1]
ans+=time_left
truck_on_brdg.popleft()
for j in range(len(truck_on_brdg)-1,-1,-1):
truck_on_brdg[j][1]-=time_left
print(ans)
갈길이 멀다.
깔끔하게 정리된 GPT의 코드를 첨부한다.
from collections import deque
def truck_on_bridge(n, w, l, trucks):
bridge = deque([0] * w) # 다리 길이만큼 0으로 채움
truck_queue = deque(trucks) # 트럭 대기열
time = 0 # 경과 시간
bridge_weight = 0 # 현재 다리 위 트럭 무게 합
while bridge: # 다리 위에 트럭이 남아있는 동안
time += 1
bridge_weight -= bridge.popleft() # 다리에서 나가는 트럭 무게 제거
if truck_queue: # 대기 중인 트럭이 있다면
if bridge_weight + truck_queue[0] <= l: # 다리가 견딜 수 있는 무게 확인
new_truck = truck_queue.popleft() # 트럭 진입
bridge.append(new_truck)
bridge_weight += new_truck
else:
bridge.append(0) # 다리 공간 유지 (빈 공간)
return time
# 입력 예시
n, w, l = map(int, input().split()) # 트럭 수, 다리 길이, 최대 하중
trucks = list(map(int, input().split())) # 트럭 무게 리스트
# 결과 출력
print(truck_on_bridge(n, w, l, trucks))
그냥 실제로 다리위에 트럭이 지나가는걸 시뮬레이션으로 구현하면 된다...
반응형
'코테 > BOJ' 카테고리의 다른 글
백준 14889 [스타트와 링크] 파이썬 (0) | 2025.03.05 |
---|---|
백준 14888 [연산자 끼워넣기] 파이썬 (0) | 2025.03.05 |
백준 1182 [부분수열의 합] (0) | 2025.03.03 |
백준 1547 [공] 파이썬 (0) | 2025.03.03 |
백준 15665 [N과 M (11)] 파이썬 (0) | 2025.03.03 |