[BOJ] 17225 - 세훈이의 선물가게 (Python)

 

 

아이디어

 

상민이와 지수가 선물을 포장하는 시간을 정렬하여 순번에 따라 선물 번호를 할당한다.

 

 

풀이

 

import sys

input = sys.stdin.readline

def solution():
    A, B, N = map(int, input().split())
    S, J = [(-A+1, 0)], [(-B+1, 1)]
    total = 0
    for i in range(1, N+1):
        t, c, m = input().split()
        t, m = int(t), int(m)
        total += m
        if c == 'B':
            last = max(S[-1][0]+A, t)
            for d in range(m):
                S.append((last+A*d, 0))
        else:
            last = max(J[-1][0]+B, t)
            for d in range(m):
                J.append((last+B*d, 1))
    timeline = sorted(S[1:]+J[1:])
    S_N = []
    J_N = []
    for i in range(total):
        _, is_j = timeline[i]
        if is_j:
            J_N.append(i+1)
        else:
            S_N.append(i+1)
    print(len(S_N))
    print(*S_N)
    print(len(J_N))
    print(*J_N)

solution()