태그: 우선순위큐 - CH Blog

2021-07-20

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	1120	261	197	29.315%

문제

세훈이는 선물가게를 운영한다. 세훈이의 선물가게는 특이하게도 손님이 어떤 선물을 구매할지 선택할 수가 없다. 대신 세훈이의 취향으로 랜덤하게 준비된 선물 중 몇 개를 구매할 것인지, 파란색과 빨간색 중 어떤 색으로 포장 받을 것인지만 결정해 주문할 수 있다.

상민이와 지수는 세훈이의 가게에서 선물 포장을 맡은 아르바이트생이다. 손님들은 파란색 포장지를 원하면 상민이에게, 빨간색 포장지를 원하면 지수에게 주문을 한다. 두 사람은 각자 주문을 받으면 그때부터 포장을 시작하는데, 현재 남아있는 선물 중 가장 앞에 있는 선물을 가져와 포장하고 주문을 받은 개수만큼 이를 반복하는 형태다. 이때 선물 하나를 포장하는 데 상민이는 A초, 지수는 B초가 걸린다. 두 사람 모두 받거나 밀린 주문이 없는데 미리 선물을 가져오거나 포장하는 일은 없으며, 두 사람이 동시에 선물을 가져올 때는 알바짬이 조금 더 있는 상민이가 먼저 가져오고, 지수가 그 뒤의 선물을 가져온다.

세훈이는 어제 구매한 선물이 망가져 있다는 항의 전화를 받았다. 자신이 준비한 선물에는 문제가 없었기에 손님에게 포장지의 색을 물었지만, 손님은 자신이 받은 선물이 무엇인지만 말하며 화를 낼 뿐이었다. 어쩔 수 없이 세훈이는 어제 가게를 방문한 손님들의 주문 내역을 보고 그 선물을 누가 포장했는지 파악하려 한다.

방문한 손님의 수와 각 손님이 주문한 시각, 선택한 포장지, 포장 받을 선물의 개수가 주어졌을 때 상민이와 지수가 각자 어떤 선물들을 포장했는지 알아내는 프로그램을 작성해보자.

입력

첫 줄에 상민이가 선물 하나를 포장하는 데 걸리는 시간 A, 지수가 선물 하나를 포장하는 데 걸리는 시간 B, 어제 세훈이 가게의 손님 수 N(1 ≤ N ≤ 1,000)이 주어진다.

이후 N개의 줄에 걸쳐 1번부터 N번 손님의 주문 시각 ti(1 ≤ ti ≤ 86,400), 선택한 포장지의 색깔 ci(ci = “B”|”R”), 주문한 선물의 개수 mi(1 ≤ mi ≤ 100)가 주어진다.

ti는 가게가 오픈한 지 ti초 후에 손님이 주문했음을 뜻하며 ci는 포장지의 색깔을 의미하는 알파벳으로 “B”는 파란색을, “R”은 빨간색을 의미한다. 주어지는 입력은 시간의 흐름에 맞게 ti의 오름차순으로 주어지며, 서로 같은 시간에 주문한 손님은 없다.

출력

첫 번째 줄에 상민이가 포장한 선물의 개수를 출력한다. 이후 두 번째 줄에 상민이가 포장한 선물들의 번호를 오름차순으로 공백으로 구분하여 출력한다.

세 번째 줄에 지수가 포장한 선물의 개수를 출력한다. 이후 네 번째 줄에 지수가 포장한 선물들의 번호를 오름차순으로 공백으로 구분하여 출력한다.

서브태스크 1 (100점)

A = B = 0

A, B가 0이라는 것은 해당 아르바이트생의 포장 속도가 너무 빨라서, 주문과 동시에 해당 주문의 모든 선물 포장이 끝난다는 의미이다.

서브태스크 2 (40점)

0 ≤ A, B ≤ 300

예제 입력 1

예제 출력 1

<그림1> 예제1 시간에 따른 상민이와 지수의 행동

예제 입력 2

예제 출력 2

<그림2> 예제2 시간에 따른 상민이와 지수의 행동

출처

University > 아주대학교 > 2019 아주대학교 프로그래밍 경시대회 APC - Div.1 B번
University > 아주대학교 > 2019 아주대학교 프로그래밍 경시대회 APC - Div.2 B번
- 문제를 만든 사람: Acka, spectaclehong

알고리즘 분류

소스코드 (Heap 이용)

import sys
import heapq

input = sys.stdin.readline

s_time, j_time, customer_count = map(int, input().split())  # 상민 포장시간, 지수 포장시간, 손님수
pacakage_list = []  # 포장시작 시간 리스트
s_end, j_end = 0, 0  # 상민, 지수 포장 끝난 시간

for _ in range(customer_count):
    start_time, color, present_count = input().rstrip().split()  # 주문시각, 색깔, 개수
    start_time = int(start_time)

    if color == 'B':  # 상민

        # 상민 포장 주문시각이 포장끝난 시각보다 먼저일 경우
        # 주문시각(포장시작시각)을 포장끝난 시점으로 변경해준다.
        start_time = max(start_time, s_end)

        for i in range(int(present_count)):  # 주문 개수만큼 반복
            heapq.heappush(pacakage_list, [start_time, 'B'])  # 상민 포장시작 시간 리스트에 저장
            start_time += s_time  # 기존 포장시작시간에 포장에 걸리는 시간 더하기
            s_end = start_time  # 포장끝난 시간은 포장시작시간+포장에 걸리는 시간

    elif color == 'R':  # 지수
        start_time = max(start_time, j_end)

        for i in range(int(present_count)):
            heapq.heappush(pacakage_list, [start_time, 'R'])
            start_time += j_time
            j_end = start_time

s_present, j_present = [], []  # 상민, 지수가 포장한 선물리스트

for i in range(1, len(pacakage_list) + 1):
    present = heapq.heappop(pacakage_list)
    if present[1] == 'B':
        s_present.append(i)
    else:
        j_present.append(i)

print(len(s_present))
print(*s_present)
print(len(j_present))
print(*j_present)

소스코드 (Queue 이용)

import sys
from collections import deque

input = sys.stdin.readline

s_time, j_time, customer_count = map(int, input().split())  # 상민 포장시간, 지수 포장시간, 손님수
sangmin = deque()  # 상민 포장시작 시간 리스트
jisu = deque()  # 지수 포장시작 시간 시간 리스트
s_end, j_end = 0, 0  # 상민, 지수 포장 끝난 시간

for _ in range(customer_count):
    start_time, color, present_count = input().rstrip().split()  # 주문시각, 색깔, 개수
    start_time = int(start_time)

    if color == 'B':  # 상민
        start_time = max(start_time, s_end)
        # if start_time < s_end:  # 상민 포장 주문시각이 포장끝난 시각보다 먼저일 경우
        #     start_time = s_end  # 주문시각(포장시작시각)을 포장끝난 시점으로 변경해준다.

        for i in range(int(present_count)):  # 주문 개수만큼 반복
            sangmin.append([start_time, 'B'])  # 상민 포장시작 시간 리스트에 저장
            start_time += s_time  # 기존 포장시작시간에 포장에 걸리는 시간 더하기
            s_end = start_time  # 포장끝난 시간은 포장시작시간+포장에 걸리는 시간

    elif color == 'R':  # 지수
        start_time = max(start_time, j_end)
        # if start_time < j_end:
        #     start_time = j_end

        for i in range(int(present_count)):
            jisu.append([start_time, 'R'])
            start_time += j_time
            j_end = start_time

total_list = sangmin + jisu
total_list = sorted(total_list, key=lambda x: [x[0], x[1]])

s_present, j_present = [], []  # 상민, 지수가 포장한 선물리스트

for idx, present in enumerate(total_list):
    if present[1] == 'B':
        s_present.append(idx + 1)
    else:
        j_present.append(idx + 1)

print(len(s_present))
print(*s_present)
print(len(j_present))
print(*j_present)

문제

입력

출력