[백준] 16937. 두 스티커 (Java)

문제

16937번: 두 스티커

 

알고리즘

브루트포스

 

 

풀이

최대 100개의 스티커 중 2개의 스티커를 고르는 경우의 수는 100 * 99 / 2 = 4,950 이고,

두 스티커를 돌려서 만들 수 있는 경우의 수는 4가지 이므로 최대 4,950 * 4 = 19,800 개의 경우의 수가 있다.

따라서 모든 경우의 수를 탐색하며 최댓값을 찾는다.

 

스티커 1의 크기를 (y1, x1), 스티커 2의 크기를 (y2, x2) 라고 하면

두 스티커를 아래로 나란히 붙일 수 있을 때 ( y1 + y2 <= h 이고 Math.max(x1, x2) <= w )

혹은 두 스티커를 옆으로 나란히 붙일 수 있을 때( x1 + x2 <= w 이고 Math.max(y1, y2) <= h )

두 스티커를 겹치지 않게 붙일 수 있으므로 max 값을 두 스티커의 넓이의 합과 비교하여 갱신한다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int H = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(br.readLine());

		int[][] stickers = new int[N][2];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			stickers[i][0] = Integer.parseInt(st.nextToken());
			stickers[i][1] = Integer.parseInt(st.nextToken());
		}

		int max = 0;
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				max = Math.max(max, check(H, W, stickers[i][0], stickers[i][1], stickers[j][0], stickers[j][1]));
				max = Math.max(max, check(H, W, stickers[i][1], stickers[i][0], stickers[j][0], stickers[j][1]));
				max = Math.max(max, check(H, W, stickers[i][0], stickers[i][1], stickers[j][1], stickers[j][0]));
				max = Math.max(max, check(H, W, stickers[i][1], stickers[i][0], stickers[j][1], stickers[j][0]));
			}
		}

		System.out.println(max);
	}

	private static int check(int h, int w, int y1, int x1, int y2, int x2) {

		if (y1 + y2 <= h && Math.max(x1, x2) <= w)
			return y1 * x1 + y2 * x2;

		if (x1 + x2 <= w && Math.max(y1, y2) <= h)
			return y1 * x1 + y2 * x2;

		return 0;
	}

}