https://www.acmicpc.net/problem/25599
문제 요약
- N,N 정사각형 + 숫자가 주어짐 (N = 1000, 숫자 = 10^7)
- K,K 범위안의 숫자중 가장 큰 숫자 = 발도술
- 모든 x,y에 대해서 발도술을 수행. 모든 합 >= R (R : 10^12)
- 가장 작은 K 구하기
접근법
- K가 증가하면 합도 커지는 것은 알겠음 => 단조 증가
- 적당한 K를 이분탐색으로 찾아야하는 것도 알겠음
- 어떤 K 에서 발도술의 합을 어떻게해야 빨리 구하나?
- 구간트리 + 2차원? 2차원 배열 부분합? 슬라이딩 윈도우?
- K-1 크기의 정사각형의 최대를 알면 K를 구할수도 있겠음
- 시간 복잡도는?
- 공간 복잡도는?
- 둘 다 감당이 안됨
- 그런데 뭔가 1, 2, 4 이런 것을 해야할 것 같음!
1,2,4,... 이런 것
- 1x1 정사각형의 최대값을 알면 2x2 정사각형 최대는 알겠음 : 4개를 이어붙이면 되니까
- 마찬가지로 2, 4, 8, ... 도 이어붙이면 구해나갈 수 있겠음
- 그런데 최대값은?
- 13x13을 구한다고 치면 8, 4, 1로 쪼개서 구해야하나? 시간복잡도는?
- 그런데 생각해보면 최대값을 구하는 것이라서 겹쳐도 됨
- 8x8의 최대값은 알고 있으니까 적당히 겹치면 13x13의 최대값을 구할 수 있음
- 공간 복잡도는? 1000x1000x10
- 시간복잡도는?
- 2^10 = 1024 ==> 1000
- 배열을 구성할때 : 1000x1000x10
- 한번 구할때 : 1000x1000
- 이분탐색을 하면서 구할때 : 10x1000x1000
newbieski