아직 계정이 없으신가요? 회원가입

관심 Tag

Talk 등록

Dev. Talk

[인증평가 3차 기출] 교차로 문제 질문입니다.

회원사진winethaysay
54 views2023-03-04 14:41

안녕하세요.
해당 문제에서 time을 1씩 증가하다가 대기선에 차가 없을 때는 남아있는 큐의 최소 시간인 mini로 업데이트합니다.
그런데 mini의 초기값을 1e9로 하면 오답이 존재하고, int(1e9)로 하면 통과하는데
이유가 무엇일까요?

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
q= [deque() for _ in range(4)]

for i in range(n):
    time,alpha = input().split()
    q[ord(alpha)-ord("A")].append((int(time),i))

result = [-1]*n
time = -1
is_waiting = [0]*4

while q[0] or q[1] or q[2] or q[3]:
    mini = 1e9

    for i in range(4):
        if q[i]:
            mini = min(mini, q[i][0][0])
            if q[i][0][0] <= time:
                is_waiting[i] = 1

    total = sum(is_waiting)
    ##교착상태
    if total == 4:
        break
    ##대기선에 차가 없을 때때
    if total == 0:
        time = mini
        continue
    
    for i in range(4):
        if is_waiting[i] and not is_waiting[i-1]:
            _,index = q[i].popleft()
            result[index] = time
    
    for i in range(4):
        is_waiting[i] = 0
    time += 1


for res in result:
    print(res,end='\n')