05. FENCE

알고리즘문제해결전략 p189

 

 

문제

 

울타리 잘라내기 (문제ID:FENCE, 난이도 중)

알고스팟 링크

 

 

풀이

 

개인적으로 분할정복 문제는 아직 어려워서 고생을 좀 했다.

분할정복 문제가 으레 그렇듯이 나누는 개념 자체는 어렵지 않다.

 

가운데를 자르고 앞의 절반의 최대값과 뒤의 절반의 최대값을 구해 비교한다.

물론 이 때 분할되는 부분을 처리해주어야 한다.

즉, 잘리는 부분의 울타리 2개를 포함하는 최대값을 구해서 같이 비교해 주어야 한다.

 

이 때, 이 가운데 부분을 처리하는 부분이 주된 문제인데

절반씩 줄어드므로 logN번 반복되는 연산으로 이 연산을 N시간에 해내야 NlogN으로 풀 수 있다.

 

내가 처리한 방법은 가운데 2개의 울타리에서 시작해서 좌우로 넓어지면서 최대값을 구하는 것이다. 이때 커지는 방향을 고정해주어야 쓸데없는 반복없이 연산되므로 어느 방향으로 넓어질지를 정해주여야 한다.

나는 현재 계산된 울타리의 왼쪽 울타리와 오른쪽 울타리를 비교해서 더 큰 울타리가 있는 방향으로 넓어지게 했다. 이 경우 다른 경우로 확장했을 때랑 비교했을때 반드시 같거나 넓음이 보장된다.

 

(파워 포인트로 대충 어떤식으로 진행되는지 GIF이미지를 만들어 보았다..)

 

중요한 점은 이렇게 N번의 연산을 하면서 그 중 최대값을 찾아야 한다는 것이다.

좌우로 뻗어나가면서 반드시 넓어진다는 보장이 없으므로 주의하자.

재귀적으로 절반씩 계속 범위를 좁혀나가면 결국에 울타리 1개의 넓이가 될 것이므로  해당 넓이를 반환하면 된다.

나는 2개의 울타리가 남은 경우도 더 이상 재귀로 넣지 않고 탈출하도록 코딩했다.

 

코드