인상 후 통행료 = 기존 통행료 + (도로 개수 * 인상분)입니다. 따라서, 인상 횟수별로가 아닌 도로 개수별로 최소 통행료들을 구해놓으면 필요한 메모리는 O(KN)에서 O(N^2)으로 줄고, 세금 인상을 처리하는 시간은 O(KN)으로 늘지만 시간 초과를 받을 정도는 아닙니다.
13907번 - 세금
인상 후 통행료 = 기존 통행료 + (도로 개수 * 인상분)입니다. 따라서, 인상 횟수별로가 아닌 도로 개수별로 최소 통행료들을 구해놓으면 필요한 메모리는 O(KN)에서 O(N^2)으로 줄고, 세금 인상을 처리하는 시간은 O(KN)으로 늘지만 시간 초과를 받을 정도는 아닙니다.
댓글을 작성하려면 로그인해야 합니다.
mintuchel 1년 전
반례는 통과되는거 같은데 메모리 초과가 나네요
근데 여기서 어떻게 더 메모리 절약할 수 있을지를 도저히 모르겠습니다...
int dist[30002][SIZE];
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
이 둘 중 하나 때문인 것 같은데
총 세금 올리는 횟수와 그에 따른 각 노드까지의 최소비용을 구하려면 2차원 배열은 필수적인 것 같고
다익스트라 돌리기 위해서는 pq도 필수인 것 같은데 어떻게 메모리 초과가 안나게 할 수 있을까요?
도와주시면 감사하겠습니다!!