백준 16937 두 스티커 c++ (완전탐색)

문제 출처 : https://www.acmicpc.net/problem/16937

16937번: 두 스티커

문제

크기가 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

알고리즘 분류

• 구현
• 브루트포스 알고리즘
• 기하학

풀이

내가 구현/완전 탐색에 약한 건지, 난이도가 잘못된 건지.. 

2021.09.29 - [알고리즘 문제 풀이/백준] - 백준 9079 동전 게임 c++ (bfs)

이 문제도 그렇고, 둘 다 실버 4의 난이도는 아닌 것 같다!!!

처음엔 스티커를 여러 개 붙여야 하는 줄 알고 막막했는데,

다시 읽어보니 두 개의 스티커만 붙이면 됐다.

그러면 풀이 자체는 간단하다.

주어진 스티커들을 가로 세로 뒤집은 모양까지 포함하여 2개의 스티커로 이루어진 조합을 만들고, 

그 조합을 모눈종이에 붙일 수 있는지 검사한 후, 붙일 수 있는 조합들에 대하여 가장 큰 크기를 찾으면 된다.

 

우선 본인은 스티커를 입력받을 때, 스티커의 가로 세로가 다르다면 뒤집은 모양도 저장했다.

pair<pair<int,int>,int> sticker[] 배열에 스티커의 가로, 세로, 원래의 스티커 번호를 저장하고, 인덱스는 가로 세로 뒤집은 모양을 포함한 총 스티커의 번호를 의미한다.

이후, dfs를 이용한 조합 알고리즘으로 2개의 스티커를 고르는데, 가로 1 세로 2인 스티커와 이 스티커를 뒤집은 가로 2 세로 1인 스티커를 고르면 안 되기 때문에, sticker에 저장해둔 스티커 번호가 방문 처리되어 있다면 스킵했다.

2개의 스티커를 고르고, 이제 이 스티커를 붙이는 2가지 방법 모두 모눈종이에 붙일 수 있는지 확인해야 한다.

우선, 가로로 스티커를 붙이는 경우, 두 스티커의 가로 합이 w보다 크면 안 되고, 두 스티커의 세로 중 큰 값이 h보다 크면 안 된다. 

세로로 스티커를 붙이는 경우, 두 스티커의 세로 합이 h보다 크면 안 되고, 두 스티커의 가로 중 큰 값이 w보다 크면 안  된다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
//1<= h,w,n<=100
//1<=r,c<=100
int h, w, n;
pair<pair<int,int>,int> sticker[200];
bool visited[100];
pair<int,int> stk[2];
int answer;
//스티커는 두 개만 붙인다.
//n이 1인 경우 스티커가 한 개이니 0 출력
//스티커 두 개 붙일 수 없는 경우 0 출력
//가로로 붙이는 경우 두 스티커의 가로 합이 w보다 작, 두 스티커 중 세로가 큰 게 h보다 작
//세로로 붙이는 경우 두 스티커의 세로 합이 h보다 작, 두 스티커 중 가로가 큰 게 w보다 작

void check() {
	//가로로 붙이기
	if(stk[0].second+stk[1].second<=w && max(stk[0].first,stk[1].first)<=h){
		answer = max(answer, stk[0].first*stk[0].second + stk[1].first*stk[1].second);
	}
	//세로로 붙이기
	if (stk[0].second+stk[1].second<=h && max(stk[0].first,stk[1].first)<=w) {
		answer = max(answer, stk[0].first*stk[0].second + stk[1].first*stk[1].second);
	}
}
void combination(int idx, int size, int cnt) {
	if (cnt == 2) {
		check();
		return;
	}
	for (int i = idx; i < size; i++) {
		int nextR = sticker[i].first.first;
		int nextC = sticker[i].first.second;
		int stkNum = sticker[i].second;
		if (visited[stkNum]) continue;
		visited[stkNum] = true;
		stk[cnt] = { nextR,nextC };
		combination(idx + 1, size, cnt + 1);
		stk[cnt] = { 0,0 };
		visited[stkNum] = false;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//input
	cin >> h >> w >> 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 << answer;
	return 0;
}