사용자 도구

사이트 도구


ps:problems:boj:14908

구두 수선공

ps
링크acmicpc.net/…
출처BOJ
문제 번호14908
문제명구두 수선공
레벨골드 1
분류

그리디

시간복잡도O(nlogn)
인풋사이즈n<=1000
사용한 언어Python 3.11
제출기록31256KB / 44ms
최고기록40ms
해결날짜2023/05/25

풀이

  • Exchange argument 를 통해 그리디한 풀이를 도출해낼수 있다.
  • 현재 시간이 t0일때,
    • i번⇒j번 순서로 고르고 나면 시간은 t0+Ti+Tj 이고, 벌금은 t0*Si +(t0+Ti)*Sj
    • j번⇒i번 순서로 고르고 나면 시간은 t0+Ti+Tj 이고, 벌금은 t0*Sj +(t0+Tj)*Si
  • t0*Si +(t0+Ti)*Sj < t0*Sj +(t0+Tj)*Si 이라면 i번⇒j번 순서대로 골라야 한다.
  • 식을 정리하면 T_i/S_i < T_j/S_j 이므로, (T_i/S_i) 기준으로 정렬하면 된다.
  • 시간복잡도는 정렬에 드는 O(nlogn)에 바운드된다.
  • 소방서의 고민도 처음 식은 좀 달라보이지만, 결국 같은 식으로 정리되는 문제이다

코드

"""Solution code for "BOJ 14908. 구두 수선공".

- Problem link: https://www.acmicpc.net/problem/14908
- Solution link: http://www.teferi.net/ps/problems/boj/14908

Tags: [greedy]
"""

import sys


def main():
    N = int(sys.stdin.readline())
    T_and_S = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    answer = sorted(range(N), key=lambda x: T_and_S[x][0] / T_and_S[x][1])

    print(*(x + 1 for x in answer))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Y K H​ U A
 
ps/problems/boj/14908.txt · 마지막으로 수정됨: 2023/05/25 05:12 저자 teferi