백준 16937번 두 스티커

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

16937번: 두 스티커

 

 

 

 

 

 

<접근방법>

모눈종이의 범위안에서 좌표마다 고려해주는 완전탐색으로 하면 시간초과가 납니다.

 

스티커는 2개만 붙입니다.

그러므로 스티커를 붙이는 형태를 강제할 수 있습니다.

1, 2 가 각각의 스티커라고 가정했을 때,

 

1 2 

혹은

1

2

 

이렇게 말이죠.

 

단, 스티커가 회전하는 것도 고려해야 합니다.

 

<느낀 점>

 

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct point {
	int y, x;
};

int n, m, k, res;
vector<point> s;
vector<point> v;

void simul() {
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			point a = v[0], b = v[1];

			if (i == 1) swap(a.y, a.x);
			if (j == 1) swap(b.y, b.x);

			int y, x;

			//1번
			y = max(a.y, b.y);
			x = a.x + b.x;

			if (y <= n && x <= m) {
				res = max(a.y*a.x + b.y*b.x, res);
			}

			//2번
			y = a.y + b.y;
			x = max(a.x, b.x);

			if (y <= n && x <= m) {
				res = max(a.y*a.x + b.y*b.x, res);
			}
		}
	}
}

void select(int dep, int start) {
	if (dep == 2) {
		simul();
		return;
	}

	for (int i = start; i < k; i++) {
		v.push_back(s[i]);
		select(dep + 1, i +1);
		v.pop_back();
	}
}


int main() {
	cin >> n >> m;
	cin >> k;
	for (int i = 0, a, b; i < k; i++) {
		cin >> a >> b;
		s.push_back({ a, b });
	}
	
	select(0, 0);

	cout << res << '\n';

	return 0;
}