문제 링크 : https://www.acmicpc.net/problem/16937
16937번: 두 스티커
첫째 줄에 모눈종이의 크기 H, W, 둘째 줄에 스티커의 수 N이 주어진다. 다음 N개의 줄에는 스티커의 크기 Ri, Ci가 주어진다.
www.acmicpc.net
문제
크기가 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);
}
}
'Algorithm(BOJ) > Brute Force' 카테고리의 다른 글
| [C++] 백준 17085번 - 십자가 2개 놓기 (완전 탐색) (0) | 2021.08.14 |
|---|---|
| [C++] 백준 2671번 - 잠수함 식별 (정규 표현식, 완전 탐색) (0) | 2021.07.06 |
| [Java] 백준 1107번 - 리모컨 (완전 탐색) (0) | 2021.05.14 |
| [C++] 백준 15686번 - 치킨 배달 (DFS / 중복조합 - 시간초과 해결) (0) | 2021.04.11 |
| [C++] 백준 16943번 - 숫자 재배치 (완전탐색 / DFS) (0) | 2021.04.05 |
