[Brute Force] 두 스티커

예제 입력 1

2 2

2

1 2

2 1

예제 출력 1

4

예제 입력 2

10 9

4

2 3

1 1

5 10

9 11

예제 출력 2

56

예제 입력 3

10 10

3

6 6

7 7

20 5

예제 출력 3

0

 

 

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

16937번: 두 스티커

- 직접 배열에 붙여보면서 하지 않아도 된다. 스티커는 주어진 스티커에서 2개만 뽑아서 가장 넓게 붙여라는 것이 문제의 조건이었으므로, 아래와 같이 Case #1, #2로 모눈종이 안에 들어오는지 체크하고 들어온다면 넓이를 계산하여 최대값을 저장한다.

#include <stdio.h>

constexpr int MAX_STICKER_SIZE = 100;

int H, W;
int N;

int finalResult = 0;

inline int MAX(int a, int b)
{
	return a > b ? a : b;
}

class sticker
{
public:
	int w;
	int h;

	sticker() {}
	sticker(int h, int w) : h(h), w(w) {}

	int getArea()
	{
		return w * h;
	}

	sticker reverse()
	{
		sticker result(w, h);
		return result;
	}

	static int getMergedArea(sticker s1, sticker s2)
	{
		int result = 0;

		// case #1
		int hSum = MAX(s1.h, s2.h);
		int wSum = s1.w + s2.w;

		if ((H >= hSum) && (W >= wSum))
		{
			result = MAX(result, s1.getArea() + s2.getArea());
		}

		// case #2
		hSum = s1.h + s2.h;
		wSum = MAX(s1.w, s2.w);

		if ((H >= hSum) && (W >= wSum))
		{
			result = MAX(result, s1.getArea() + s2.getArea());
		}

		return result;
	}
};
sticker s[MAX_STICKER_SIZE];
bool selected[MAX_STICKER_SIZE];

template <typename T>
class vector
{
public:
	T item[2];
	int size;

	vector() { size = 0; }

	void push(T i)
	{
		item[size] = i;
		size++;
	}

	T pop()
	{
		T result = item[size - 1];
		size--;

		return result;
	}
};
vector<sticker> v;

void go(int start, int cnt, vector<sticker> &v)
{
	if (cnt == 2)
	{
		// v1 v2
		finalResult = MAX(finalResult, sticker::getMergedArea(v.item[0], v.item[1]));

		// v1 뒤집고 v2
		finalResult = MAX(finalResult, sticker::getMergedArea(v.item[0].reverse(), v.item[1]));

		// v1 v2 뒤집고
		finalResult = MAX(finalResult, sticker::getMergedArea(v.item[0], v.item[1].reverse()));

		// v1 뒤집고 v2 뒤집고
		finalResult = MAX(finalResult, sticker::getMergedArea(v.item[0].reverse(), v.item[1].reverse()));

		return;
	}

	for (int i = start; i < N; i++)
	{
		v.push(s[i]);
		go(i + 1, cnt + 1, v);
		v.pop();
	}
}

int main(void)
{
	scanf("%d %d", &H, &W);
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		int h, w;
		scanf("%d %d", &s[i].w, &s[i].h);
	}

	go(0, 0, v);

	printf("%d\n", finalResult);

	return 0;
}