울타리 잘라내기(난이도 - 중)
1. 문제 설명
(1) 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다.
(2) 시간이 지남에 따라 판자들이 망가져 높이가 다 달라져서 기존의 울타리 일부를 직사각형으로
잘라내 재활용하고 싶습니다.
(3) 이때, 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를
계산하는 프로그램을 작성하세요.
( (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. )
( 단, (c) 처럼 비스듬히 잘래날 수 없습니다. )
2. 입출력 조건 및 예제
입력 조건
(1) 판자의 수 N(1<=N<=20000)이어야 한다.
(2) 높이는 모두 10,000 이하의 자연수입니다.
출력 조건
(1) 각 테스트 케이스당 정수 하나를 한 줄에 출력합니다.
입력 예제
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
3. 제약 조건
(1) 프로그램은 1초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다.
4. 가정법
X
5. 기저 사례
(1) 판자가 하나밖에 없는 경우
( 즉, left == right )
6. 코드
: 두 코드가 존재한다.
(1)의 코드는 무식하게 접근하여 해결하는 방법을 보여준다. 그냥 단순하게 l번 판자에서 r번 판자까지 잘라내서
사각형을 만드는 넓이를 계산하는 이중 for문을 작성하는 것이다. 그러나, 입력의 최대 크기는 20,000번이므로
시간복잡도 O(n^2)으로는 힘들어 보입니다.
( (1)의 코드는 아래의 코드를 이용한 것입니다. )
그러므로, 우리는 (2)의 코드처럼 분할 정복 알고리즘을 설계해야 합니다.
설계는 먼저 양쪽을 분할하는 부분 문제 2개와 양쪽 부분을 걸치는 부분 문제 1개로 아래처럼 나눠서 진행합니다.
( (1) 가장 큰 직사각형을 왼쪽 부분 문제에서만 잘라낼 수 있다. )
( (2) 가장 큰 직사각형을 오른쪽 부분 문제에서만 잘라낼 수 있다. )
( (3) 가장 큰 직사각형은 왼쪽 부분 문제와 오른쪽 부분 문제에 걸쳐 있다. )
이때, (3)에서는 경계선 기준으로 양쪽의 판자를 하나씩 포함하며 확장한다.
( 단, 왼쪽을 먼저 확장할 것인지 오른쪽을 먼저 확장할 것인지는 판자 크기순으로 정한다. )
(1) Brute-Force
public class Fence1 {
private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer st ;
private static StringBuilder builder = new StringBuilder();
public static void main(String[] args) throws IOException {
int c = Integer.parseInt(sc.readLine());
for(int i=0; i<c; i++) {
int N = Integer.parseInt(sc.readLine());
int[] h = new int[N];
st = new StringTokenizer(sc.readLine());
for(int j=0; j<N; j++) {
h[j] = Integer.parseInt(st.nextToken());
}
builder.append(bruteForce(h) + "\n");
}
System.out.println(builder);
}
// 무식하게 접근하는 방식
// (b-a+1) * (min(h[i]) 이때, h[i]는 가장 작은 원소
private static int bruteForce(int[] h) {
int ret=0;
int N = h.length;
for(int left=0; left<N; left++) {
int minH = h[left];
for(int right=left; right<N; right++) {
minH = Math.min(minH, h[right]);
ret = Math.max(ret, (right-left+1)*minH);
}
}
return ret;
}
}
(2) 분할 정복
public class Fence2 {
private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer st ;
private static StringBuilder builder = new StringBuilder();
private static int[] h;
public static void main(String[] args) throws NumberFormatException, IOException {
int c = Integer.parseInt(sc.readLine());
for(int i=0; i<c; i++) {
int N = Integer.parseInt(sc.readLine());
h = null;
h = new int[N];
st = new StringTokenizer(sc.readLine());
for(int j=0; j<N; j++) {
h[j] = Integer.parseInt(st.nextToken());
}
builder.append(solve(0, N-1) + "\n");
}
System.out.println(builder);
}
private static int solve(int left, int right) {
// 기저사례: 판자가 하나일 경우 그대로 값 리턴
if(left == right) return h[left];
// 주어진 원소를 중간으로 나누고
// 초기에 중간을 기준으로 왼쪽과 오른쪽으로 계속 분할
int mid = (left+right) / 2;
int ret = Math.max(solve(left, mid), solve(mid+1,right));
// 중간을 기준으로 양쪽에 걸쳐서 존재하는
// 직사각형을 위해 분할
int lo=mid, hi=mid+1;
int height = Math.min(h[lo], h[hi]);
// height의 값은 양쪽에서 걸쳐서 존재하기에
// 직사각형을 그리기 때문에 *2 필요
ret = Math.max(ret, height*2);
// 먼저, lo와 hi가 left, right 부분으로 옮길 수 없다면, 종료
while(lo<left || hi<right) {
// h[lo-1]<h[hi+1]이라면, hi를 옮김
// 아니라면 lo를 옮김
if(hi<right && (lo==left || h[lo-1] < h[hi+1])) {;
height = Math.min(height, h[++hi]);
}else {
height = Math.min(height, h[--lo]);
}
// 최종적으로 값 계산
ret = Math.max(ret, height * (hi-lo+1));
}
return ret;
}
}
7. 시간 복잡도
- 문제를 항상 절반으로 나누어서 재귀 호출(O(lgn))하고, 후처리 계산을 하는 반복문(O(n))이 있다.
- 이 시간 복잡도는 병합 정렬과 같은 시간 복잡도 O(nlgn)을 가지게 된다.
( n=20,000 -> nlgn은 290,000 이기 떄문에 아주 쉽게 1초 안에 풀 수 있다. )