문제로 바로가기

아 너무 어렵다. 다이나믹 프로그래밍을 이용. 다이나믹 프로그래밍은 이전에 계산했던 것을 버리지 않고 계속 이용하는 것. 12 점 받았다. 제일 많이 받은 것 같은데
fun compute(board, y, before, cur)

compute 함수는 y 열의 각 행에서 밑으로 연속되는 정사각형의 개수를 ls 에 저장한다.

이런 사각형이 있다면
compute(0), compute(1),compute(2),compute(3) 을 한 결과는

매번 ls 를 계산하는 대신 compute 함수는 y-1 열의 ls 를 전달받아 거기에서 -1을 하며 값이 0보다 작을 때만 (연속된 사각형이 끊겼을 때에만 ) 다시 각 행에서 연속되는 사각형의 개수를 계산한다.

ls를 이용하여 가장 큰 정사각형을 찾는 코드는

m = max(ls)
    if m <= cur:
        return ls, 0
for d in range(cur, m+1):
        count = 0
        for i in ls:
            if i >= d:
                count += 1
            else:
                count = 0
            if count >= d:
                rec = max(d, rec)

cur 은 solution 으로부터 전달받은 이전까지 계산한 가장 큰 정사각형. 이보다 작은 정사각형이 존재하는 지는 계산할 필요가 없다.

improve

답안

똑똑한 사람이 너무 많다. 각 점을 오른쪽 끝으로 하는 정사각형의 개수를 board 에 저장한다.