아래 <그림 1>과 같이 직사각형 모양의 종이가 있다. 이 종이는 가로방향과 세로 방향으로 1㎝마다 점선이 그어져 있다. 가로 점선은 위에서 아래로 1번부터 차례로 번호가 붙어 있고, 세로 점선은 왼쪽에서 오른쪽으로 번호가 붙어 있다. [그림 1]
점선을 따라 이 종이를 칼로 자르려고 한다. 가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한 번에 자른다. 예를 들어, <그림 1>의 가로 길이 10㎝이고 세로 길이 8㎝인 종이를 3번 가로 점선, 4번 세로 점선, 그리고 2번 가로 점선을 따라 자르면 <그림 2>와 같이 여러 개의 종이 조각으로 나뉘게 된다. 이때 가장 큰 종이 조각의 넓이는 30㎠이다. [그림 2]
입력으로 종이의 가로 세로 길이, 그리고 잘라야할 점선들이 주어질 때, 가장 큰 종이 조각의 넓이가 몇 ㎠인지를 구하는 프로그램을 작성하시오.
입력
첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지한 줄에 점선이 하나씩 아래와 같은 방법으로 입력된다. 가로로 자르는 점선은 0과 점선 번호가 차례로 주어지고, 세로로 자르는 점선은 1과 점선 번호가 주어진다. 입력되는 두 숫자 사이에는 빈 칸이 하나씩 있다.
출력
첫째 줄에 가장 큰 종이 조각의 넓이를 출력한다. 단, 넓이의 단위는 출력하지 않는다.
예제 입력/출력
예제 입력
예제 출력
10 8 3 0 3 1 4 0 2
30
알고리즘 분류
● 정렬
소스코드
package Lv2_Silver;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
/**
* @author HanHoon
* @category 정렬
* https://www.acmicpc.net/problem/2628
*/
public class BOJ_S5_2628_종이자르기 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
// 종이의 가로길이
int width = Integer.parseInt(st.nextToken());
// 종이의 세로길이
int height = Integer.parseInt(st.nextToken());
// 칼로 잘라야하는 점선의 개수
int N = Integer.parseInt(br.readLine());
ArrayList<Integer> widthCut = new ArrayList<>();
ArrayList<Integer> heightCut = new ArrayList<>();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
// 0: 가로, 1:세로
int a = Integer.parseInt(st.nextToken());
if(a == 0)
widthCut.add(Integer.parseInt(st.nextToken()));
else if(a == 1)
heightCut.add(Integer.parseInt(st.nextToken()));
}
widthCut.add(0);
widthCut.add(height);
heightCut.add(0);
heightCut.add(width);
Collections.sort(widthCut);
Collections.sort(heightCut);
// 가로 자르기 후 최대 세로 길이
int x = 0;
int y = 0;
for (int i = 1; i < widthCut.size(); i++) {
int tmp = widthCut.get(i) - widthCut.get(i-1);
y = y < tmp ? tmp : y;
}
// 세로 자르기 후 최대 가로 길이
for (int i = 1; i < heightCut.size(); i++) {
int tmp = heightCut.get(i) - heightCut.get(i-1);
x = x < tmp ? tmp : x;
}
System.out.println(x*y);
br.close();
}
}
댓글