[Algorithm🧬] 백준 5464 : 주차장

문제

처음에 당연히 시간 비례 주차장인 줄 알고 시간 + 무게 다 넣고 짰는데... 아니었따. 시간 계산을 위해 idx 를 포함해서 짰는데, 해당 부분을 다 없애버리면 될 것 같다.

import sys
from collections import deque

readl = sys.stdin.readline
n, m = map(int, readl().split()) # 주차 공간 수 / 차량 수
fee = [int(readl()) for _ in range(n)] # 단위 무게당 요금. (자리)
weight = [int(readl()) for _ in range(m)] # 차량의 무게
orders = [int(readl()) for _ in range(2*m)] # 차량이 들어오고 나가고. 1은 1이 들어온거 -1 은 1이 나간거.


q = deque()
parking_count = 0
ch = [(0, 0, 0, 0) for _ in range(n)] # 자리는 index 로 구분 하고 (차량 번호, 시작 시간, 자리 당 단위 요금, 무게) 순으로 저장.
total = 0


for idx, car in enumerate(orders):
    if car > 0:
        # 빈자리가 있으면 자리에 넣고
        if parking_count < n:
            for i, c in enumerate(ch):
                if c == (0, 0, 0, 0):  # 빈자리
                    ch[i] = (car, idx, fee[i], weight[car - 1])
                    parking_count += 1
                    break
        # 빈 자리가 없으면 큐에 넣음.
        else:
            q.append(car)
    else:
        num, start_time, f, w = 0, 0, 0, 0
        # 해당 차량을 찾아서 정보 저장 후 초기화.
        for i in range(n):
            # 이미 들어왔던 차가 나가고
            if ch[i][0] == -car:
                num, start_time, f, w = ch[i]
                ch[i] = (0, 0, 0, 0)
                parking_count -= 1
                # 큐에서 기다리는 것이 있었다면 해당 차를 세움.
                if q:
                    ca = q.popleft()
                    ch[i] = (ca, idx, fee[i], weight[ca - 1])
                    parking_count += 1
                break
        
        # total += (idx - start_time) * f * w # 시간 비례인 줄....
		total += f * w


print(total)

시간 부분 저장을 없앤 코드

import sys
from collections import deque

readl = sys.stdin.readline

n, m = map(int, readl().split())
주차장자리 = [int(readl()) for _ in range(n)]
차의무게 = [int(readl()) for _ in range(m)]
출입순서 = [int(readl()) for _ in range(2 * m)]

ch = [0] * n

q = deque()
total = 0
빈자리 = -1

for 차번호 in 출입순서:
    if 차번호 > 0:
        # 자리가 있으면 자리에 넣고
        for i in range(n):
            if ch[i] == 0:
                ch[i] = 차번호
                break
        # 자리가 없으면 큐에 넣고
        else:
            빈자리 = -1
            q.append(차번호)

    else:
        차번호 = -차번호
        for i in range(n):
            if ch[i] == 차번호:
                ch[i] = 0
                빈자리 = i

                total += 주차장자리[i] * 차의무게[차번호 - 1]

                break
        if q:
            for i in range(n):
                if ch[i] == 0:
                    ch[i] = q.popleft()
                    break


print(total)