ksjb2897   1년 전

다이나믹 프로그래밍으로 풀었습니다.

일단 2차원을 1차원으로 바꿔도 상관없어서 1차원 배열로 만들었습니다. 그 후, 이 1차원 배열을 qsort를 이용하여 정렬해줍니다.

그러고나서 전체 블럭개수를 전체 칸의 개수로 나눠서 최대 층을 구합니다(이 값이 max)

그다음 다이나믹 프로그래밍을 이용하여

층마다, 그 층보다 작은 높이를 가진 칸의 개수와 그 층보다 큰 높이를 가진 칸의 개수를 구합니다.(left가 작은 높이를 가진 칸, right 가 높은 높이를 가진 칸)

그러고 나서 f를 다이나믹 프로그래밍으로 층마다의 드는 시간으로 구해줍니다.

그러고 최솟값을 구합니다...

보시면 while이 없어서 무한루프문제도 아닌 것 같고,

시간복잡도가 정렬에 쓰이는 NlogN(N의 최댓값은 25000)가 최대일텐데,

(나머지는 전부 O(N)혹은 O(max)...)

왜 시간초과가 날까요...??? 이해불가능 ㅠㅠ

ksjb2897   1년 전

저는 바보인가요?

500*500 = 250000인데요 하하

25000으로 했네요

댓글을 작성하려면 로그인해야 합니다.