골드 III

문제

겨울이 좋아

풀이

$i$번째 나무의 나뭇잎이 전부 떨어지는 데에는 $\lceil A_i / B_i \rceil$일이 걸립니다. 정우의 능력은 이 날을 하루 당기는 것으로 생각할 수 있습니다.

아이디어

우선순위 큐에 $\lceil A_i / B_i \rceil$을 모두 넣고 최댓값을 빼내 $1$을 빼고 다시 넣는 것을 반복 횟수가 큐의 최댓값보다 커지기 전 까지 반복하는 방법을 생각해 볼 수 있습니다.

하지만 $A_i / B_i \le 10^9$이므로 시간 초과를 받습니다. 따라서 $1$씩 감소시키는 것 보다 빠른 방법을 사용해야 합니다.

개선

$\lceil A_i / B_i \rceil$을 배열에 담고 내림차순으로 정렬하여 이를 $T_i$라 합시다. 능력을 사용하여 $T_1$을 $T_2$와 같게 만들고, $T_1, T_2$를 $T_3$과 같게 만들고, $\dots$

$T_1, \dots, T_i$를 $T_{i + 1}$과 같게 만드는 것을 반복하면 됩니다.

능력을 사용한 총 횟수를 $U$라 합시다. 문제의 정답을 $a$라 합시다. 초기에 $U = 0$, $a = T_1$로 초기화합니다.

$i = 1$부터 $i = N - 1$까지 아래를 반복합니다.

$T_1, \dots, T_i$를 $T_{i + 1}$와 같게 만들기 위해 사용해야 하는 능력의 횟수 $r$을 계산합니다.
이전 반복문에서 $T_1 = \dots = T_i$로 만들었으므로 $r = (T_i - T_{i + 1})i$입니다.
능력을 $r$번 사용하는 것이 가능한 경우 $U$와 $a$의 값을 갱신합니다.
$U$에는 $r$을 더하고, $a$에는 $r$을 빼면 됩니다.
$U + r > a - (T_i - T_{i + 1})$인 경우 나뭇잎이 다 떨어지고 나서도 능력을 써야하는 상황이므로 $r$번 능력을 사용할 수 없습니다.
그렇지 않은 경우 사용 가능한 능력의 최댓값을 다시 계산하여 $U$와 $a$의 값을 갱신하고 반복문을 끊습니다.
$i$개의 나무를 모두 $d$일 당긴다고 하면 $U + id \le a - d$을 만족해야 하므로 $d \le (a - U) / (i + 1)$ 입니다.

반복문이 모두 끝나고 나면 모든 $T$값을 얼마까지 감소시킬 수 있는지 마지막으로 계산해야 합니다.

이를 코드를 추가적으로 작성하는 대신 $T_{N + 1} = 0$을 추가하고 $i = N$까지 반복하여 마지막 반복에서 알아서 계산되도록 할 수 있습니다.

코드

def main():
    N = int(input())

    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    time = sorted([-(-A[i] // B[i]) for i in range(N)], reverse=True)
    time.append(0)

    total_ability_count = 0
    answer = time[0]

    for i in range(N):
        diff = time[i] - time[i + 1]
        if diff == 0:
            continue

        required = diff * (i + 1)

        if total_ability_count + required <= answer - diff:
            total_ability_count += required
            answer -= diff
        else:
            diff = (answer - total_ability_count) // (i + 2)
            answer -= diff
            break

    print(answer)


main()

백준 32984번: 겨울이 좋아 [Python]

문제

풀이

아이디어

개선

코드

백준 32984번: 겨울이 좋아 [Python]