[python] algospot FENCE 문제풀이

문제

-> 문제 링크 : https://algospot.com/judge/problem/read/FENCE

algospot.com :: FENCE

 

문제풀이

판자의 수가 최대 20000이기에 모든 위치를 탐색하며 그 위치에 해당하는 최대 넓이를 구하려고 한다면 O(N^2)이 나와 시간 초과가 된다. 그렇기에 N인 모든 위치를 탐색하지 않는 방법이 필요하다.

 

분할 정복 방법을 이용해서 N인 탐색범위를 줄여보자.

전체 막대 수에서 반을 갈라보자. 그렇다면 최대 크기의 직사각형이 만들어지는 위치는 3개 중에 한 곳이 된다.

1. 반으로 잘랐을 때 왼쪽에만 위치 2. 오른쪽에만 위치 3. 왼쪽과 오른쪽에 걸쳐서 있음

 

재귀를 이용하면 쉽게 구현이 가능하다.

[0,A]의 영역을 탐색한다면 재귀를 불러 왼쪽과 오른쪽에만 위치하는 경우에 해당되는 [0,A/2], [A/2+1,0]을 다음 재귀에서 탐색하도록 보내고,  현재 재귀에서는 A/2, A/2+1 블록을 동시에 포함하면서 가장 큰 영역을 계산해주면 된다.

 

이를 반복하다보면 재귀의 깊이는 log2(N)이 최대가 된다.

한 재귀의 깊이에서 발생할 수 있는 최대 연산 횟수는 N이므로  (  깊이가 4라면 n/8 영역을 8개의 함수에서 검사하니 n )

모든 영역을 검사하는데 걸리는 시간은 O(NlogN)이 된다.

 

현재 재귀에서 푸는 문제 즉, A/2, A/2+1 블록을 동시에 포함하는 가장 큰 영역을 구하는 함수만 짜면 문제는 해결된다.

반복문을 통해 구현이 가능하다. left는 중간에서 시작한 직사각형의 맨 왼쪽을 가리키고, right는 맨 오른쪽을 가리킨다.

제일 끝을 가리키는 left, right의 다음에 있는 인덱스 값을 비교해서 더 높은 쪽으로 이동한다.

그렇게 하면 왼쪽 오른쪽으로 직사각형은 넓어지지만 높이는 높은 수에서 낮은 수로 순서대로 이동한다.

 

이렇게 구한 넓이와 오른쪽, 왼쪽 영역에서 가장 큰 넓이 중 큰 넓이를 선택하면 최대 직사각형의 넓이가 된다.

 

코드

import sys

T = int(sys.stdin.readline().rstrip())

def divide(start, end) :

    if start == end :
        return fence[start]

    left = ( start + end ) // 2
    right = left + 1

    leftMax = divide(start,left)
    rightMax = divide(right, end)

    block_cnt = 2
    minHeight = min(fence[left], fence[right])
    midMax = minHeight * block_cnt

    while start < left or right < end :

        if start == left :
            right += 1
            minHeight = min(minHeight,  fence[right])

        elif right == end :
            left -= 1
            minHeight = min(minHeight, fence[left])

        elif fence[left-1] >= fence[right+1] :
            left -= 1
            minHeight = min(minHeight,  fence[left])

        elif fence[left-1] < fence[right+1] :
            right += 1
            minHeight = min(minHeight, fence[right])

        block_cnt += 1
        midMax = max( midMax, block_cnt * minHeight)

    return max(leftMax, midMax, rightMax)

for _ in range(T) :

    N = int(sys.stdin.readline().rstrip())
    fence = list(map(int, sys.stdin.readline().rstrip().split()))

    print(divide(0,N-1))

초기 접근 방식과 오답의 원인

각 블록 위치에서 시작하는 최대 블록의 넓이를 계산하면 O(N^2)이 나온다는 사실은 알았지만, 

더 이상 시간 복잡도를 줄이는 방법을 생각해내지 못했다.

 

최대 넓이가 존재할 수 있는 위치를 통해 3가지로 나눌 수 있다는 방법을 생각해내지 못했다.

분할을 어떻게 해야할지 감이 잡히질 않아 문제를 제대로 풀어보지 못했다.

 

 

 

코드에 잘못된 부분이나 개선 사항이 있다면 댓글로 알려주시면 감사하겠습니다.