[Silver 3] 16937 두 스티커

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

16937번: 두 스티커

 

이 문제는 조합을 통한 완전 탐색을 이용하면 해결할 수 있다.

문제에서 두 개의 스티커만 이용하라고 되어 있어, 2 개의 스티커를 고르면 가로나 세로로 붙인 결과의 최대 값을 출력하면 된다.

 

입력된 스티커의 가로, 세로 값과 90도 회전할 수 있으면 회전한 가로, 세로 값을 배열에 삽입한다.

회전 가능한 스티커는 가로, 세로 값이 같지 않은 스티커만 가능하다.

또한 뒤집은 스티커와 뒤집지 않은 스티커를 고르지 않게 해야한다. 즉, 동일한 스티커를 고르지 않게 해야한다. 

위 조건을 만족하도록 배열을 pair 형태로 선언하고 배열에 삽입 시 스티커 번호도 삽입하면 된다.

 

조합시 동일한 스티커를 고르지 못하도록 visited 배열에 스티커 번호에 따라 방문 표시를 하고 고른 스티커의 가로, 세로 값을 삽입한다.

2개의 스티커를 골랐다면 붙인 스티커의 넓이를 구한다. 

이때 넓이를 구할 경우 가로와 세로로 스티커를 붙여 넓이를 구할 수 있다.

가로로 스티커를 붙이는 경우 선택한 스티커의 가로 합(C의 합)이 W를 벗어나지 않아야한다. 또한 선택한 스티커의 세로 최대 값이 H를 벗어나지 않아야한다.

세로로 스티커를 붙이는 경우 선택한 스티커의 세로 합(R의 합)이 H를 벗어나지 않아야한다. 또한 선택한 스티커의 가로 최대 값이 W를 벗어나지 않아야한다.

 

두 개의 스티커를 통해 넓이를 구하였다면 방문 표시를 없애고 선택한 스티커를 초기화하여 다음 스티커를 선택할 준비를 하면 된다.

 

#include<iostream>
#include<string>
using namespace std;

int H, W, N;
pair<pair<int, int>, int> sticker[200];
bool visited[100];
pair<int, int> selected[2];
int result = 0;

void check() {
	
	if (selected[0].second + selected[1].second <= W) {
		if (max(selected[0].first, selected[1].first) <= H) {
			result = max(result, selected[0].first * selected[0].second + selected[1].first * selected[1].second);
		}
	}
	if (selected[0].second + selected[1].second <= H) {
		if (max(selected[0].first, selected[1].first) <= W) {
			result = max(result, selected[0].first * selected[0].second + selected[1].first * selected[1].second);
		}
	}
	
}
void combination(int idx, int size, int counter) {
	if (counter == 2) {
		check();
		return;
	}
	for (int i = idx; i < size; i++) {
		int r = sticker[i].first.first;
		int c = sticker[i].first.second;
		int target = sticker[i].second;

		if (visited[target]) continue; // 스티커 중복 선택 방지
		visited[target] = true;
		selected[counter] = { r,c };

		combination(idx + 1, size, counter + 1);
		selected[counter] = { 0,0 };
		visited[target] = false;
	}
	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> H>>W;
	cin >> N;

	int idx = 0;
	for (int i = 0; i < N; i++) {
		int R, C;
		cin >> R >> C;
		sticker[idx++] = { {R,C},i };
		if (R != C) {
			sticker[idx++] = { {C,R},i };
		}
	}
	combination(0, idx, 0);
	cout << result << '\n';
	return 0;
}