백준 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$로 고정했다고 하자. 그..
백준 21275번 폰 호석만
문제 요약 문자열 A, B가 주어진다. 두 문자열이 각각 A진법, B진법으로 표현되어 있다고 했을 때 10진법으로 바꾼 숫자를 A', B'라고 하자. A' = B' 이면서 A != B인 (A,B)가 정확히 하나 있다면 그 숫자와 A, B를 출력하고 두 개 이상이라면 Multiple, 없다면 Impossible을 출력하자. 이 때, $ 0 \le A', B' \lt 2^{63}$을 만족해야 한다. $ 2 \le A, B \le 36$ 주어지는 문자열의 길이는 최대 70이다. 풀이 어떤 문자열을 $B$진법으로 표현되어 있다고 가정하고 10진법으로 변환하는 것은 문자열의 길이만큼 시간이 걸린다. 따라서, 주어진 두 문자열을 2진법부터 시작해서 36진법까지 전부 바꿔 ..