🔍문제

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 512 MB 607 294 246 48.617%

문제

지금 구두 수선공에게는 손님으로부터 주문 받고 제작해야 할 작업이 N개 쌓여있다. 구두 수선공은 하루에 한 작업만 수행할 수 있고, i번째 작업을 완료하는 데 Ti일이 걸린다. 이때 Ti는 정수이고 1 ≤ Ti ≤ 1000이다.

i번째 작업을 시작하기 전에 하루가 지연될 때마다 구두 수선공은 보상금 Si센트를 지불해야 한다. 이때 Si는 정수이고 1 ≤ Si ≤ 10000이다. 구두 수선공을 돕기 위해 최저 보상금을 지불하는 작업 순서를 정해야 한다.

하루에 2개 이상의 작업을 동시에 수행할 수 없다. 작업 i를 수행하고 있는 경우, 작업 i를 마칠 때 까지 작업 i 외의 다른 작업을 수행할 수 없다.

입력

1 ≤ N ≤ 1000 범위의 정수 N이 첫 번째 줄에 주어진다. 다음 N개 줄에 걸쳐서 첫 번째 열에는 T1 … TN이 입력되며, 두 번째 열에는 S1 … SN이 주어진다.

출력

최소 보상금을 지불하는 작업 순서를 출력해야 한다. 모든 작업은 입력에서의 번호(1~N)로 표시해야 한다. 모든 정수는 한 줄로 표시해야 하며, 각 작업은 공백 문자로 구분한다. 여러 가지 해답이 나올 수 있다면 오름차순 정렬에 의해 가장 첫 번째 해답을 출력한다.

예제 입력 1 복사

1
2
3
4
5
4
3 4
1 1000
2 2
5 5

예제 출력 1 복사

1
2 1 3 4

📝내 풀이

1
2
3
4
5
6
7
8
9
10
11
12
N = int(input())
weightList = []

totalTime = 0
for i in range(N):
    t, s = map(int, input().split())
    weightList.append([t/s,i+1])

weightList.sort()

for w in weightList:
    print(w[1], end=" ")

BOJ 카테고리 내 다른 글 보러가기

댓글남기기