문제

https://www.acmicpc.net/problem/16937

풀이

참고자료

• https://yabmoons.tistory.com/278
• https://ongveloper.tistory.com/268

1. N개의 스티커에 대해 원본과 회전한 모양까지 포함하여 {{가로, 세로}, 스티커 번호} 이렇게 스티커에 대한 정보를 묶어서 배열에 저장한다. (단, 가로, 세로 길이가 동일한 스티커는 회전해도 모양이 동일하기 때문에, 회전한 스티커 정보는 저장하지 않는다.)

2. 조합을 이용하여 배열에 저장된 스티커 중에서 2개를 선택한다. 단, 동일한 스티커인데 방향만 다른 경우를 선택하지 않도록 따로 처리해준다. (그래서 위의 단계에서 스티커 번호를 같이 저장한 것이다.)

• 동일한 스티커인데 방향만 다른 경우: {{1, 2}, 0} {{2, 1}, 0}
• 참고로, 2개의 스티커를 뽑는 순서는 상관이 없기 때문에 순열이 아니라 조합이다.

3. 뽑은 2개의 스티커를 모눈종이에 같이 붙일 수 있는지 검사한다.

2개의 스티커를 모눈종이에 붙이는 방법은 아래 두 가지 경우의 수밖에 없다.

두 스티커가 모눈종이 안에서 조금 떨어져있든, 대각선 방향으로 이어 붙이든, 두 개의 스티커가 어떤 식으로든 모눈종이 안에 쏙 들어가면 되기 때문이다!

1) 가로 방향으로 이어 붙이는 경우

• A의 가로 길이 + B의 가로 길이 <= 모눈종이의 가로 길이
• A와 B 중에 더 긴 세로 길이 <= 모눈종이의 세로 길이

2) 세로 방향으로 이어 붙이는 경우

• A의 세로 길이 + B의 세로 길이 <= 모눈종이의 세로 길이
• A와 B 중에 더 긴 가로 길이 <= 모눈종이의 가로 길이

C++ 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string> 
#include <stack> 
#include <queue> 
#include <set>
using namespace std;
typedef pair<int, int> pii; 

const int MAX = 101; 
int H, W, N;
vector<pair<pii, int>> sticker; // 회전한 모양까지 포함하여 저장 
bool selected[MAX]; // 백트래킹에 사용 
int arr[2]; // 선택된 2개의 스티커 인덱스 저장 
int answer = 0; 

void checkTwoStickerSize() {
	int firstH = sticker[arr[0]].first.first; 
	int firstW = sticker[arr[0]].first.second; 
	int firstArea = firstH * firstW;

	int secondH = sticker[arr[1]].first.first; 
	int secondW = sticker[arr[1]].first.second; 
	int secondArea = secondH * secondW; 

	if(firstH + secondH <= H && max(firstW, secondW) <= W){ 
		answer = max(answer, firstArea + secondArea); 
	}

	if(firstW + secondW <= W && max(firstH, secondH) <= H){ 
		answer = max(answer, firstArea + secondArea); 	
	}
}

void dfs(int idx, int cnt){
	// 2개를 선택한 경우에 대한 처리 
	if(cnt == 2){
		checkTwoStickerSize();
		return; 
	}

	// 조합이므로 i는 idx부터 시작함. (한번 선택한 원소는 돌아보지 않음.) 
	for(int i = idx; i < sticker.size(); i++){
		int height = sticker[i].first.first; 
		int width = sticker[i].first.second; 
		int num = sticker[i].second; 

		if(!selected[num]){
			// 상태 변화
			selected[num] = true; 

			// cnt번째로 선택된 스티커 인덱스 저장 
			arr[cnt] = i; 

			// 재귀 호출 
			dfs(i, cnt + 1); 

			// 상태 복구
			selected[num] = false; 
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
    cin.tie(0);
	 
	cin >> H >> W >> N;

	for(int i = 0; i < N; i++){
		int r, c; 
		cin >> r >> c; 
		
		sticker.push_back({{r, c}, i});
		
		if(r != c){
			sticker.push_back({{c, r}, i});
		}
	}

	dfs(0, 0);

	cout << answer; 

	return 0;
}