백준 10227 - 삶의 질 [Python]

https://www.acmicpc.net/problem/10227

10227번: 삶의 질

[알고리즘 분류]

이분 탐색, 누적 합

 

 

정답을 \(x\)라고 가정하자.

주어진 배열에서 \(x\)보다 큰 수는 1, 작은 수는 -1로 바꾼다면, 합이 0인 \(H\) x \(W\) 직사각형이 배열 내에 존재할 것이다.

 

이 아이디어를 이용하여 이분 탐색으로 적절한 \(x\)를 찾을 수 있고, 시간복잡도 \(O(RC(lg(RC)))\)에 문제를 풀 수 있다.

 

75줄부터 보면 된다.

import sys, math
import heapq
 
from dataclasses import dataclass
from collections import deque
from bisect import bisect_left, bisect_right
 
input = sys.stdin.readline
 
hqp = heapq.heappop
hqs = heapq.heappush
 
 
# input
def ip(): return int(input())
def sp(): return str(input().rstrip())
 
 
def mip(): return map(int, input().split())
def msp(): return map(str, input().split().rstrip())
 
 
def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split()))
 
 
# gcd, lcm
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
 
 
def lcm(x, y):
    return x * y // gcd(x, y)
 
 
# prime
def isPrime(x):
    if x <= 1: return False
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return False
    return True
 
 
# Union Find
# p = [i for i in range(272727)]
 
def find(x):
    if x == p[x]:
        return x
    p[x] = find(p[x])
    return p[x]
 
 
def union(x, y, s):
    x = find(x)
    y = find(y)
 
    if x != y:
        p[y] = x
 
 
def getPow(a, x):
    ret = 1
    while x:
        if x & 1:
            ret = (ret * a) % MOD
        a = (a * a) % MOD
        x >>= 1
    return ret
 
 
############ Main! #############
 
n, M, h, w = mip()
a = []
p = [[0 for _ in range(3003)] for _ in range(3003)]
pf = [[0 for _ in range(3003)] for _ in range(3003)]
 
ans = 10**9
for i in range(n):
    a.append(lmip())
 
lo = 0
hi = 10000000
while lo <= hi:
    m = (lo + hi) // 2
    for i in range(n):
        for j in range(M):
            if a[i][j] <= m:
                p[i][j] = -1
            else:
                p[i][j] = 1
    for i in range(n):
        for j in range(M):
            pf[i][j] = pf[i-1][j] + pf[i][j-1] - pf[i-1][j-1] + p[i][j]
    fl = False
    g = False
    for i in range(h - 1, n):
        if fl: break
        for j in range(w - 1, M):
            if pf[i][j] - pf[i-h][j] - pf[i][j-w] + pf[i-h][j-w] <= 0:
                fl = True
                break
    if fl:
        hi = m - 1
    else:
        lo = m + 1
 
print(lo)
 
######## Praise greedev ########

시간이 어마어마하다..!