Processing math: 100%

본문 바로가기

학부/알고리즘응용 (실습)

(1)

[알고리즘응용 실습] CSES - Reading Books [문제 설명] 책의 개수 n과 책을 읽는 데에 걸리는 시간 t1, t2, ..., tn이 주어졌을 때, Kotivalo(이하 K)와 Justiina(이하 J)가 모든 책을 읽는 데에 걸리는 시간의 최솟값을 구하는 문제 [해결 방법] 입력받은 수열 t1, t2, ..., tn에 대해 최댓값 M과, 수열의 합 sum을 정의하여 2 × M와 sum 중 큰 값을 출력하였다. [Correctness] K와 J가 각각 모든 책을 다 읽는 시간이 sum임은 당연하다. 그렇다면 K와 J가 동시에 읽는다면 어떻게 되는지 확인해보겠다. 우선 수열

$t_1,t_2,...,t_n$ 을 내림차순으로 정렬시키고 K와 J는 그 순서대로 읽는다고 가정하겠다. K는

$t_1$ 부터, J는

$t_2$ 부터 읽는다고 할 때, 모든 i에 대해 ..

티스토리툴바