[Java] 백준 16937번 - 두 스티커 (완전 탐색, 중복 조합)

문제 링크 : https://www.acmicpc.net/problem/16937

16937번: 두 스티커

 

문제

크기가 H×W인 모눈종이와 스티커 N개가 있다. i번째 스티커의 크기는 Ri×Ci이다. 모눈종이는 크기가 1×1인 칸으로 나누어져 있으며, 간격 1을 두고 선이 그어져 있다.

오늘은 모눈종이에 스티커 2개를 붙이려고 한다. 스티커의 변은 격자의 선과 일치하게 붙여야 하고, 두 스티커가 서로 겹치면 안 된다. 단, 스티커가 접하는 것은 가능하다. 스티커를 90도 회전시키는 것은 가능하다. 스티커가 모눈종이를 벗어나는 것은 불가능하다.

두 스티커가 붙여진 넓이의 최댓값을 구해보자.

입력

첫째 줄에 모눈종이의 크기 H, W, 둘째 줄에 스티커의 수 N이 주어진다. 다음 N개의 줄에는 스티커의 크기 Ri, Ci가 주어진다.

출력

첫째 줄에 두 스티커가 붙여진 넓이의 최댓값을 출력한다. 두 스티커를 붙일 수 없는 경우에는 0을 출력한다.

제한

• 1 ≤ H, W, N ≤ 100
• 1 ≤ Ri, Ci ≤ 100

 

 

---

접근 방법

N개의 스티커 중 DFS 함수를 이용해 2개를 고른다. 이 때 중복 조합을 이용해 중복을 제거한다.

고른 2개의 스티커에 대해 총 4가지 경우를 따져서 스티커를 붙일 수 있는지 검사해야한다.

 

1) 둘 다 그대로

2) 1번 스티커만 회전

3) 2번 스티커만 회전

4) 둘 다 회전

 

각 경우에 대해 위 아래로 붙였을 때와 좌우로 붙였을 때 모두 검사해서 하나라도 모눈종이 안에 들어온다면 스티커 두개 넓이를 계산한다.

 

import java.util.*;
 
class Pair16937{
	Integer h, w;
	public Pair16937(Integer _h, Integer _w) {
		this.h = _h;
		this.w = _w;
	}
	public Integer getHeight() {
		return this.h;
	}
	public Integer getWidth() {
		return this.w;
	}
}
 
public class BF_BOJ16937_두스티커 {
	
	static int H, W, N;
	static int[] visited = new int[100];
	static ArrayList<Pair16937> pairList = new ArrayList<Pair16937>();
	static ArrayList<Pair16937> tmpList = new ArrayList<Pair16937>();
	static int maxi = 0;
	
	static boolean chkHeight(int h1, int w1, int h2, int w2) {		//위 아래로 붙였을 때 
		if(h1+h2 > H || Math.max(w1, w2) > W) return false;
		else return true;
	}
	static boolean chkWidth(int h1, int w1, int h2, int w2) {		//양옆으로 붙였을 때 
		if(Math.max(h1, h2) > H || w1 + w2 > W) return false;
		else return true;
	}
	
	static boolean chkHW(int h1, int w1, int h2, int w2) {
		if(chkHeight(h1,w1,h2,w2)==true || chkWidth(h1,w1,h2,w2)==true) return true;
		else return false;
	}
	
	
	static void DFS(int toPick, int start) {
		
		if(toPick==0) {
			int h1 = tmpList.get(0).getHeight();
			int w1 = tmpList.get(0).getWidth();
			
			int h2 = tmpList.get(1).getHeight();
			int w2 = tmpList.get(1).getWidth();
			
			//1번 그대로, 2번 그대로 
			boolean chk = false;
			if(chkHW(h1,w1,h2,w2) == true) {	
				int area = h1*w1 + h2*w2;
				if(maxi<area) maxi = area;
				chk = true;
			}
			else {
				for(int i = 0; i<3; i++) {
					int a,b,c,d;
					if(i==0) {				//1번 회전, 2번 그대로
						a = w1; b = h1;
						c = h2; d = w2;
					}
					else if(i==1) {			//1번 그대로, 2번 회전
						a = h1; b = w1;
						c = w2; d = h2;
					}
					else {					//1번 회전, 2번 회전 
						a = w1; b = h1;
						c = w2; d = h2;
					}
					if(chkHW(a,b,c,d)==true) {
						chk = true;
						int area = h1*w1 + h2*w2;
						if(maxi<area) maxi = area;
						return;
					}
				}
			}
			
			return;
		}
		
		for(int i = start; i<pairList.size(); i++) {
			
			if(visited[i]==0) {
				visited[i] = 1;
				tmpList.add(pairList.get(i));
				DFS(toPick-1, i);
				tmpList.remove(tmpList.size()-1);
				visited[i] = 0;
			}
		}
	}
	
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		H = sc.nextInt();
		W = sc.nextInt();
		N = sc.nextInt();
		for(int i = 0; i<N; i++) {
			int h = sc.nextInt();
			int w = sc.nextInt();
			pairList.add(new Pair16937(h,w));
		}
		
		DFS(2,0);
		
		System.out.print(maxi);
	}
}