백준 21343번 Great Expectation
문제 스피드런을 진행하려고 한다. $n, r, m$이 주어지는데 $n$은 이상적으로 진행했을 때의 걸리는 시간이고 $r$은 깨고자 하는 기록이다. 즉, 전체 시간을 $r$보다 작게 스피드런을 끝내고 싶다. 스피드런 도중에는 $m$개의 이벤트가 있는데 이 이벤트에 성공하면 그대로 진행하는 것이고, 실패하면 추가적으로 시간을 사용하게 된다. 이벤트에 대한 정보는 $t, p, d$로 주어지는데 각각 이벤트가 일어날 시각, 성공확률, 실패 시 추가로 드는 시간이다. 스피드런 도중에 언제든지 리셋을 할 수 있다. 이런 상황에서 전체 진행시간을 $r$보다 짧게 만드는 데 걸릴 시간의 기댓값을 구하시오. $ 2 \le n \lt r \le 5000$, $ 1 \le m \le 50$, $ 1 \le t \lt n$,..
백준 16318번 Delivery Delays
문제 요약 정점 $n$개, 간선 $m$개의 무방향 그래프가 주어진다. 해당 그래프의 1번 노드에 피자집이 있다. $k$개의 피자 주문이 들어오는데 각 주문은 $s_i, u_i, t_i$로 들어오는데 각각 주문이 들어온 시각, 주문이 들어온 노드의 번호, 해당 주문의 피자가 완성되는 시간이다. 이 피자들을 주문이 들어온 순서대로 배달하려고 한다. 시각 0에 1번 정점에 위치하며, 들고다닐 수 있는 피자의 수에 제한은 없다. 이 때, 각 주문의 대기시간의 최댓값을 최소화 하여라. $ n \le 1000$, $ m \le 5000$, $ k \le 1000$, $ 0 \le s_i \le t_i \le 10^8 $ 풀이 들고다닐 수 있는 피자의 수에 제한이 없으므로 피자집에서 다른 피자가 준비 완료될 때까지 ..
백준 21279번 광부 호석
문제 요약 점 $(X_i, Y_i)$가 $N$개 주어진다. 이 때, $(0, 0)$을 왼쪽 아래 꼭짓점으로 하고 $(H, W)$를 오른쪽 위 꼭짓점으로 하는 직사각형을 그리고자 한다. 이 때, 직사각형에 포함되는 점의 개수는 최대 $C$개이다. 각 점에 대응하는 가치인 $V_i$도 주어지는데 조건을 만족하는 직사각형 중에서 포함되는 점들의 가치의 합이 최대가 되게 그렸을 때의 그 최댓값을 출력해야 한다. $ 1 \le N \le 500,000$, $1 \le C \le N$, $ 0 \le X_i, Y_i \le 100,000$, $1 \le V_i \le 10^8$ 풀이 우리가 그리고자 하는 직사각형의 오른쪽 위 꼭짓점을 위주로 풀이를 진행해보자. 이 꼭짓점의 $y$좌표를 $a$로 고정했다고 하자. 그..
