문제
너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. 단 (c)처럼 직사각형을 비스듬히 잘라낼 수는 없습니다.
판자의 너비는 모두 1이라고 가정합니다.
입력
첫 줄에 테스트 케이스의 개수 C (C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 판자의 수 N (1≤N≤20000)이 주어집니다. 그 다음 줄에는 N개의 정수로 왼쪽부터 각 판자의 높이가 순서대로 주어집니다. 높이는 모두 10,000 이하의 음이 아닌 정수입니다.
출력
각 테스트 케이스당 정수 하나를 한 줄에 출력합니다. 이 정수는 주어진 울타리에서 잘라낼 수 있는 최대 직사각형의 크기를 나타내야 합니다.
예제 입력
3
7
7 1 5 9 6 7 3
7
1 4 4 4 4 1 1
4
1 8 2 2
예제 출력
20
16
8
Concept
처음 접했을 때, 굉장히 난해해 보이는 문제였다. 반복문만 돌리는 brute force만 써서는 시간초과가 날 것이 뻔해 어느정도의 재귀를 통해 구현하려 했다.
교재의 아이디어를 참고하여 내가 작성해본 코드는 다음과 같다.
#include <iostream>
#include <vector>
using namespace std;
int arr[20001];
int fence(int start, int end){ // 0 6
if (start==end) return arr[start];
if (start+1==end) return 2*min(arr[start], arr[end]);
int mid = (start+end)/2;
//case 1 : 기준(mid)의 왼쪽에서만 답이 생길 경우
int Square1=fence(start, mid-1);
//case 2 : 기준의 오른쪽에서만 답이 생길 경우
int Square2=fence(mid+1, end);
//case 3 : 기준이 포함되어 답이 생길 경우
int Square3=-1, rect;
for (int i=start; i<=mid; i++){ // i는 직사각형의 가장 왼쪽
for (int j=mid; j<=end; j++){ // j는 직사각형의 가장 오른쪽
int minHeight=10001;
for (int k=i; k<=j; k++){ //k는 i~j까지의 가장 낮은 높이를 구하기 위함
if (arr[k] < minHeight) minHeight = arr[k];
}
rect = minHeight*(j-i+1);
if (Square3<rect) Square3 = rect;
}
}
return (Square1>Square2) ? ((Square1>Square3)? Square1 : Square3) : ((Square2>Square3)? Square2 : Square3);
}
int main(){
int c;
cin>>c;
for (int h=0; h<c; h++){ // case별
int n;
cin>>n;
for (int i=0; i<n; i++){
cin>>arr[i];
}
// 0 1 2 3 4 5 6
// 7 1 5 9 6 7 3
cout<<fence(0, n-1)<<endl;
}
}예제는 잘 돌아갔으나 결과는 시간초과였다.
도저히 모르겠어 인터넷을 통해 검색해보니 위의 for문을 2개나 사용한 것이 원인인 것으로 결론났다.
mid의 왼쪽, 오른쪽을 각각의 index를 통해 선형적으로 확정해가면 시간복잡도 O(n)으로 해결할 수 있었던 것을 굳이 for문을 2개 사용해가며 시간복잡도가 O(n^2)가 된 것이었다.
인터넷의 코드를 참고한 결과, 다음과 같이 작성하여 통과할 수 있었다.
Code
#include <iostream>
#include <vector>
using namespace std;
int arr[20001];
int fence(int start, int end){ // 0 6
if (start==end) return arr[start];
if (start+1==end) return 2*min(arr[start], arr[end]);
int mid = (start+end)/2;
//case 1 & 2 : 기준(mid)의 왼쪽, 오른쪽에서만 답이 생길 경우
int Square1=max(fence(start, mid-1), fence(mid+1, end));
//case 3 : 기준이 포함되어 답이 생길 경우
int height = arr[mid];
int width = 1;
int Square2= max(Square1, height*width);
int l = mid-1;
int r = mid+1;
//선형적으로 탐색한다. (O(n))
while(start<=l || r <=end){
if (start > l || (arr[l] <= arr[r] && r <= end)){ // right이 더크면
height = min(height, arr[r]); // 오른쪽으로 넓힌다.
r++; //그다음 index update
width++;
Square2 = max(Square2, width*height);
}
else if (r > end || (arr[l]>= arr[r] && start<=l)){ // left가 더 크면
height = min(height, arr[l]); // 왼쪽으로 넓힌다.
l--;
width++;
Square2 = max(Square2, width*height);
}
else break; //왼쪽 index와 오른쪽 index가 둘 다 범위를 벗어나면 종료.
}
return Square2;
}
int main(){
int c;
cin>>c;
for (int h=0; h<c; h++){ // case별
int n;
cin>>n;
for (int i=0; i<n; i++){
cin>>arr[i];
}
// 0 1 2 3 4 5 6
// 7 1 5 9 6 7 3
cout<<fence(0, n-1)<<endl;
}
}
Comment
저렇게 while문을 이용해 index를 선형적으로 넓혀나가는 문제는 생소하였다.
항상 배열의 크기에 유의하고, 선형적 접근법을 익혀두자.
근데 이 코드는 틀렸다. 여기를 보자...
