16937 두 스티커

두 스티커

 Silver V
난이도 제공: solved.ac

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

512 MB

1072

367

262

35.262%

문제

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

 

풀이)

1. 스티커 N개중 2개를 뽑아서 스티커를 가로 세로 돌려보며 붙여본다음 최대값을 찾는다.

 

2. 시간 복잡도 .1) 스티커 N개중 2개 뽑는 방법 nC2 = 100c2 == 100*99 *

                    2) 스티커 2개를 가로세로로 돌리는 방법 2^2 = 4가지

                    3)  2)에서 회전 시킨 스티커 2개를 옆으로 이어 붙일껀지, 아래로 이어붙일껀지 = 2가지 

  O 4*2(N^2) = 대략 O(8N^2)  { O(8*100*99) } 

 

3.  1)스티커 N개중 2개 뽑는방법 -> 재귀로 구현, 또는 순열을 이용한 0과 1로 컴비네이션 (조합)을 구현 (필자는 재귀)

 

4.  2)스티커를 가로세로로 돌리는방법 r =1 c=2 라면 (1,2) 를 세로로 돌리면 (2,1)이된다. swap을 해주면 됨.

 

5.  3)옆으로 이어 붙일껀지 아래로 붙일건지에 대한 설명

빨간 1번의 경우 아래로 이어 붙인것 , 이 경우 y2값이 W 범위내 (x1+x2)값이 H 범위내에 존재하면 가능.

 

빨간 2번의 경우옆으로 이어 붙인것  , 이 경우 (y1+y2)값이 W범위내 x1 값이 H범위내에 존재하면 가능.

 

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

int H,W,N;
vector<pair<int, int>> v;

bool check[100];
void go(int index, int cnt);
int ans = 0;

int main(void)
{
	cin >> H >> W;
	cin >> N;

	int x, y;
	for (int i = 0; i < N; ++i)
	{
		cin >> x >> y;
		v.push_back(make_pair(x, y));
	}

	go(0, 0);
	cout << ans << '\n';
	return 0;
}
void go(int index, int cnt)
{
	if (cnt == 2)
	{
		int x1, y1, x2, y2;
		bool isSecond = false;
		for (int i = 0; i < N; ++i)
		{
			if (check[i])
			{
				if (isSecond == false)
				{
					x1 = v[i].first;
					y1 = v[i].second;
					isSecond = true;
				}
				else 
				{
					x2 = v[i].first;
					y2 = v[i].second;
				}
					
			}		
		}
		//스티커 붙이기
		//붙이는것이 가능한지 (가로 ,세로) swap
		//붙은 스티커의 넓이합
		//넓이 합이 최대값인지

		//스티커 붙이기 어떻게 붙일 것인가.
		// 2개의 스티커 가로세로 =2^2 (4가지)
		//ㅡㅣ ㅡㅡ ㅣㅣ ㅣㅡ 4가지
		//세로로 연속해서 붙이냐, 가로로 연속해서 붙이냐 (2가지)
		for (int q = 0; q < 2; ++q)
		{
			for (int w = 0; w < 2; ++w)
			{
				//세로로 붙일때
				if (x1+x2 <= H && max(y1, y2) <= W)
				{
					int sum = (x1 * y1) + (x2 * y2);
					if (ans < sum)
						ans = sum;
				}
				// 가로로 붙일때
				else if (max(x1,x2) <= H && y1 + y2 <= W)
				{
					int sum = (x1 * y1) + (x2 * y2); 
					if (ans < sum)
						ans = sum;
				}
				swap(x2, y2);
			}
			swap(x1, y1);
		}
		return;
	}

	for (int i = index; i < N; ++i)
	{
		if (check[i]==false)
		{
			check[i] = true;
			go(i+1, cnt + 1);
			check[i] = false;
		}
		
	}
}