[백준 2628] 종이자르기 (C++)

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

문제

---

아래 <그림 1>과 같이 직사각형 모양의 종이가 있다. 이 종이는 가로방향과 세로 방향으로 1㎝마다 점선이 그어져 있다. 가로 점선은 위에서 아래로 1번부터 차례로 번호가 붙어 있고, 세로 점선은 왼쪽에서 오른쪽으로 번호가 붙어 있다.

 

<그림 1>

점선을 따라 이 종이를 칼로 자르려고 한다. 가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한 번에 자른다. 예를 들어, <그림 1>의 가로 길이 10㎝이고 세로 길이 8㎝인 종이를 3번 가로 점선, 4번 세로 점선, 그리고 2번 가로 점선을 따라 자르면 <그림 2>와 같이 여러 개의 종이 조각으로 나뉘게 된다. 이때 가장 큰 종이 조각의 넓이는 30㎠이다.

 

<그림 2>

입력으로 종이의 가로 세로 길이, 그리고 잘라야할 점선들이 주어질 때, 가장 큰 종이 조각의 넓이가 몇 ㎠인지를 구하는 프로그램을 작성하시오.

 

입력

---

첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 줄에 점선이 하나씩 아래와 같은 방법으로 입력된다. 가로로 자르는 점선은 0과 점선 번호가 차례로 주어지고, 세로로 자르는 점선은 1과 점선 번호가 주어진다. 입력되는 두 숫자 사이에는 빈 칸이 하나씩 있다.

 

출력

---

첫째 줄에 가장 큰 종이 조각의 넓이를 출력한다. 단, 넓이의 단위는 출력하지 않는다.

 

문제 풀이

---

정렬 문제.

 

종이 조각의 개수는 가로로만 잘라서 만들어진 종이 조각의 개수 * 세로로만 잘라서 만들어진 종이 조각의 개수가 된다. 따라서 가장 큰 종이 조각의 넓이는 가로로 잘랐을 때 만들어지는 종이조각 중 가장 긴 길이 * 세로로만 잘랐을 때 만들어지는 종이조각 중 가장 긴 길이가 된다.

길이가 8cm이고 2cm와 3cm에서 자른다면, 0-2 / 2-3 / 3-8의 구간으로 나눌 수 있다. 따라서 종이조각의 길이는 2, 1, 5가 만들어진다. 0과 끝인 8을 벡터에 넣고 입력으로 주어진 입력 값을 모두 벡터에 넣은 후 정렬해준다. 인접한 두 수의 차이가 종이 조각의 길이가 된다.

가로, 세로 각각 잘랐을 때 모든 만들어지는 길이를 벡터에 넣고 정렬한다. 그리고 가로 길이를 저장해 둔 벡터에서 가장 큰 것, 세로 길이를 저장해 둔 벡터에서 가장 큰 것을 곱해주면 된다.

 

아래는 코드.

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

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

	int N, M, K;
	int a, b;
	cin >> N >> M;
	cin >> K;
	vector<int> v0;
	vector<int> v1;
	vector<int> garo;
	vector<int> sero;
	v0.push_back(0);
	v0.push_back(M);
	v1.push_back(0);
	v1.push_back(N);
	for (int i = 0; i < K; i++)
	{
		cin >> a >> b;
		if (a == 0)
		{
			v0.push_back(b);
		}
		else
		{
			v1.push_back(b);
		}
	}
	sort(v0.begin(), v0.end());
	sort(v1.begin(), v1.end());
	for (int i = 1; i < v0.size(); i++)
	{
		garo.push_back(v0.at(i) - v0.at(i - 1));
	}
	for (int i = 1; i < v1.size(); i++)
	{
		sero.push_back(v1.at(i) - v1.at(i - 1));
	}
	sort(garo.begin(), garo.end());
	sort(sero.begin(), sero.end());
	cout << garo.back() * sero.back() << "\n";
	return 0;
}