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

문제

 

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

<그림 1>

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

<그림 2>

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

---

입력

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

---

출력

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

---

예제 입력 1 복사

10 8 
3 
0 3 
1 4 
0 2

예제 출력 1 복사

30

---

풀이과정

접근을 어떻게 하는가가 중요했던 문제같다.

접근을 할때 기본적으로 사각형의 넓이를 구하는 공식이 사각형 넓이: 가로 X 세로 이므로 즉 가장 큰 사각형은

가장 큰 가로 * 가장 큰 세로 라는 사실을 알 수 있다. 그래서 도형을 아무리 가로로 자르고 세로로 자른다고 해도

짤린 세로 중에 가장 긴 길이 * 짤린 가로 중에 가장 긴 길이가 가장 큰 사각형을 찾는 규칙이 되게 된다.

그래서 들어있는 입력값들을 크기순으로 정렬을 한 다음, 가장 범위가 넓은 세로길이와 가장 범위가 넓은 가로길이를 곱하게 되면

문제에서 원하는 결과값을 구할 수 있게되는 문제였다.

code

#include <iostream>
#include <algorithm>
#include <vector>

// 가로 0, 세로 1
int		main(void)
{
	int		y, x, n, dir, num, rowMax = -1, columnMax = -1;
	std::vector <int> row, column;

	std::cin >> x >> y;
	std::cin >> n;
	row.push_back(0);
	row.push_back(x);
	column.push_back(0);
	column.push_back(y);
	for(int i = 0; i < n; i++) {
		std::cin >> dir >> num;
		if (dir == 1) row.push_back(num);
		else column.push_back(num);
	}
	std::sort(row.begin(), row.end());
	std::sort(column.begin(), column.end());
	
	for (int i = 0; i < row.size(); i++)
		if (row.size() > i + 1 && row[i + 1] - row[i] > rowMax)
			rowMax = row[i + 1] - row[i];
	for (int i = 0; i < column.size(); i++)
		if (column.size() > i + 1 && column[i + 1] - column[i] > columnMax)
			columnMax = column[i + 1] - column[i];
	std::cout << rowMax * columnMax;
	
	return (0);
}

---

후기

문제의 출처를 보니 초등부 올림피아드 문제더라..

저걸 보고 "요즘 초등부애들은 저런 문제를 푸는구나 대단하다" 라고 생각이 들어가지고 더 열심히 해야겠다라고 생각을 하게되었다.