[Softeer] 21년 재직자 대회 본선 - 트럭

문제

<배경>

 

<입력>

 

<출력>

<예시>

예제 1번 설명:

• 신차의 크기가 1이라면, 1번 소비자에게만 차량을 보낼 수 있으므로, 총 1원의 매출을 얻는다.
• 신차의 크기가 2이라면, 1,2번 소비자에게만 차량을 보낼 수 있으므로, 총 1+2=3원의 매출을 얻는다.
• 신차의 크기가 3이라면, 1,2,3번 소비자에게만 차량을 보낼 수 있으므로, 총 1+2+3=6원의 매출을 얻는다.
• 신차의 크기가 4이라면, 모든 소비자에게 차량을 보낼 수 있으므로, 총 1+2+3+4=10원의 매출을 얻는다.

---

풀이

이 문제에 사용될 알고리즘은 아래와 같다.

 

1. 모든 사람들의 가격제안을 차 크기 순으로 작은 것부터 정렬한다.

 

2. 제안을 하나씩 보면서 이 제안을 한 사람에게 기존에 얻을 수 있는 매출보다,

새 제안을 받아들여서 매출이 더 오른다면 매출을 업데이트한다.

 

3. 새로 업데이트된 매출로 새로 달성가능해진 시나리오가 있는지 확인하고, 있다면 그 이 제안의 차 사이즈를 답으로 기록한다.

 

 

입력처리에서 정렬까지 해 알고리즘 1번을 수행한다.

numBuyer = int(input())
offer = [] # [차size, payment, buyerID]
for i in range(numBuyer):
    temp = list(map(int, input().split()))
    for j in range(temp[0]):
        offer.append([temp[2*j+1],temp[2*j+2],i+1])

numScenario = int(input())
temp = list(map(int, input().split()))
scenario = [] # [target_revenue, targetID, size(답)]
for i in range(numScenario):
    scenario.append([temp[i],i+1])

offer.sort() #이중리스트는 앞의 값으로 정렬됨. size로 정렬
scenario.sort()# revenue로 정렬

 

알고리즘 2,3단계에 해당하는 코드이다.

마지막 while문은 모든 offer를 검토했음에도 달성할 수 없는 시나리오에 대해 답을 -1로 기록하는 과정이다.

revenue = 0
buyerPayment = [0]*(numBuyer+1) #이 사람이 낸 돈
sIndex = 0 #시나리오용 인덱스
for i in range(len(offer)):
    size = offer[i][0] #size순으로 정렬된 상태
    payment = offer[i][1]
    buyerID = offer[i][2]
    if payment > buyerPayment[buyerID]: #이사람한테 더 비싸게 받을 수 있으면
        revenue += -buyerPayment[buyerID] + payment #이전에 받았던 돈은 빼고, 새로 받은 돈 추가
        buyerPayment[buyerID] = payment

    while(sIndex < numScenario and scenario[sIndex][0] <= revenue): #이미 매출이 더 높은 경우, 이 경우는 시나리오 충족
        scenario[sIndex].append(size) #
        sIndex += 1
while(sIndex < numScenario): #-1 추가
    scenario[sIndex].append(-1)
    sIndex += 1

 

 

이후 다시 문제에서 주어진 순서대로 정렬하여 답을 출력한다.

scenario.sort(key = lambda x: x[1])
for i in range(numScenario):
    print(*scenario[i][2],end=' ')