18111번 - 마인크래프트
다이나믹 프로그래밍으로 풀었습니다.
일단 2차원을 1차원으로 바꿔도 상관없어서 1차원 배열로 만들었습니다. 그 후, 이 1차원 배열을 qsort를 이용하여 정렬해줍니다.
그러고나서 전체 블럭개수를 전체 칸의 개수로 나눠서 최대 층을 구합니다(이 값이 max)
그다음 다이나믹 프로그래밍을 이용하여
층마다, 그 층보다 작은 높이를 가진 칸의 개수와 그 층보다 큰 높이를 가진 칸의 개수를 구합니다.(left가 작은 높이를 가진 칸, right 가 높은 높이를 가진 칸)
그러고 나서 f를 다이나믹 프로그래밍으로 층마다의 드는 시간으로 구해줍니다.
그러고 최솟값을 구합니다...
보시면 while이 없어서 무한루프문제도 아닌 것 같고,
시간복잡도가 정렬에 쓰이는 NlogN(N의 최댓값은 25000)가 최대일텐데,
(나머지는 전부 O(N)혹은 O(max)...)
왜 시간초과가 날까요...??? 이해불가능 ㅠㅠ
저는 바보인가요?
500*500 = 250000인데요 하하
25000으로 했네요
댓글을 작성하려면 로그인해야 합니다.
ksjb2897 1년 전
다이나믹 프로그래밍으로 풀었습니다.
일단 2차원을 1차원으로 바꿔도 상관없어서 1차원 배열로 만들었습니다. 그 후, 이 1차원 배열을 qsort를 이용하여 정렬해줍니다.
그러고나서 전체 블럭개수를 전체 칸의 개수로 나눠서 최대 층을 구합니다(이 값이 max)
그다음 다이나믹 프로그래밍을 이용하여
층마다, 그 층보다 작은 높이를 가진 칸의 개수와 그 층보다 큰 높이를 가진 칸의 개수를 구합니다.(left가 작은 높이를 가진 칸, right 가 높은 높이를 가진 칸)
그러고 나서 f를 다이나믹 프로그래밍으로 층마다의 드는 시간으로 구해줍니다.
그러고 최솟값을 구합니다...
보시면 while이 없어서 무한루프문제도 아닌 것 같고,
시간복잡도가 정렬에 쓰이는 NlogN(N의 최댓값은 25000)가 최대일텐데,
(나머지는 전부 O(N)혹은 O(max)...)
왜 시간초과가 날까요...??? 이해불가능 ㅠㅠ