구두 수선공 (14908번) - 백준 (BOJ)

https://www.acmicpc.net/problem/14908

14908번: 구두 수선공

 

 

백준 - 구두 수선공 (14908번)

 

난이도 : Gold 1

알고리즘&자료구조 : 그리디 (Greedy) & 정렬 (Sorting)

시간복잡도 (Time Complexity) : O( N logN )

---

★ 핵심 Idea ★

 

◎ 보상금 S가 작업 소요 일수 T에 비해 클수록 먼저 수선해야 한다. (Greedy)

 

[(2, 2), (3, 4)] 두 개의 수선할 구두가 있다고 하면,

아래와 같이 (3, 4) 구두를 먼저 수선하는 경우가 보상금이 더 적다.

 

(3, 4) 먼저 수선 : 비용 6

 

(2, 2) 먼저 수선 : 비용 8

 

따라서 수선할 구두 정보들을 [(보상금 S) / (소요시간 T)] 값 기준으로 정렬하고,

위의 값이 같다면 오름차순 정렬을 위해 앞선 번호를 더 앞으로 위치시킨다.

---

 

< 전체 코드 >

 

import sys
input = sys.stdin.readline


class Repair():
    def __init__(self, N):
        arr = [(i, *map(int, input().split())) for i in range(1, N+1)]
        arr.sort(key=lambda x: (-x[2]/x[1], x[0]))
        self.odr = [seq[0] for seq in arr]


if __name__ == '__main__':
    repairs = Repair(int(input()))
    print(*repairs.odr)