사용자 도구

사이트 도구


ps:problems:boj:7744

Cakes

ps
링크acmicpc.net/…
출처BOJ
문제 번호7744
문제명Cakes
레벨플래티넘 3
분류

그리디

시간복잡도O(nlogn)
인풋사이즈n<=1,000,000
사용한 언어Python 3.11
제출기록88752KB / 2696ms
최고기록2696ms
해결날짜2023/07/28

풀이

  • Mountain Climbing 과 거의 동일한 문제. Mountain Climbing과 다른 점은, 두번째 작업을 진행하는 순서를 첫번쨰 작업을 진행한 순서와 다르게 해도 상관없다는 부분인데, 실제 풀이는 어차피 동일하다.
  • 풀이는 Mountain Climbing을 참고. 덤으로, The Milk Queue도 동일한 문제.

코드

"""Solution code for "BOJ 7744. Cakes".

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

Tags: [greedy]
"""

import sys
import functools


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

    a_and_b.sort(
        key=functools.cmp_to_key(
            lambda x, y: (
                (x[0] - x[1]) - (y[0] - y[1])
                if (comp := min(x[0], y[1]) - min(x[1], y[0])) == 0
                else comp
            )
        )
    )

    prepare_time = bake_time = 0
    for a, b in a_and_b:
        prepare_time += a
        bake_time = max(bake_time, prepare_time) + b

    print(bake_time)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
R O B H G
 
ps/problems/boj/7744.txt · 마지막으로 수정됨: 2023/07/28 01:51 저자 teferi