최소직사각형 찾기

1. 문제 설명

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

X

 

출력 조건

X

 

 

입력 예제

4

60 50

30 70

60 30

80 40

 

출력 예제

4000

 

 

 

 

3. 제약 조건

X

 

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

X

 

 

 

 

6. 코드

public class Main {
	private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
	private static StringTokenizer st;
	
	public static void main(String[] args) throws Exception {
		int c = Integer.parseInt(sc.readLine());
		int[][] A = new int[c][2];
		
		for(int i=0; i<c; i++){
			st = new StringTokenizer(sc.readLine());
			for(int j=0; j<2; j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		System.out.println(makeWallet(A));
	}
	
	private static int makeWallet(int[][] A) {
		int ret[] = new int[2];
		int max=0, min=0;
		
		for(int i=0; i<A.length; i++) {
			int a = Math.max(A[i][0], A[i][1]);
			int b = Math.min(A[i][0], A[i][1]);
			max = Math.max(max, a);
			min = Math.max(min, b);
		}
		return max*min;
	}
}

 

 

(1) 이 문제는 요약하면 모든 명함을 넣을 수 있는 가장 짧은 가로,세로 길이를 구하는 것이다.

 

(2) 단, 명함을 눕힐 수 있기 때문에 가로와 세로 길이를 바꿀 수 있다.

 

(3) 그러므로 행들끼리 비교하여  max와 min 값을 구한다.

( 주의있게 봐야 할 점은 min을 최소값으로 구하면 안 된다는 것이다. )

( 예를 들어, {70,30}과 {50, 50}이 있다면, 두 행에서의 min은 30이다. )

( 그러나 30을 한다면, 두 번째 행의 길이 50이 못 들어가게 된다. )

( 그러므로 min 중에서도 최대값을 구해야 한다. )

 

 

(4) 아래의 풀이 과정을 보고 이해하자.