[코딩테스트 C++] 종이자르기

오늘의 문제

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

종이자르기

접근 방식

• 들어오는 인자를 보면 제일 큰 사각형의 크기는, 가로, 세로 각각에서 간격이 제일 큰 부분의 곱이다.
• 그래서 가로, 세로 각각 인자를 받아 정렬한 후에, 사이 간격을 체크, 제일 큰것이 남는다.
• 그걸 곱하면 끝
• 나는 혹시 같은 값이 많이 들어올까봐 set자료형에 저장하고, 정렬시 vector에 옮겼다.
• 중복이 되어도 괜찮긴 하다. 간격이 0이면 선택될리 없으니까

나의 풀이

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#pragma warning(disable: 4996)
using namespace std;

int n, m;

int main(){
    scanf("%d %d", &n, &m);
    set<int> row, col;
    int k, a, b;
    scanf("%d", &k);
    for(int i=0;i<k ;i++){
        scanf("%d %d", &a, &b);
        if(a == 0)
            row.insert(b);
        else
            col.insert(b);
    }
    row.insert(0);
    row.insert(m);
    col.insert(0);
    col.insert(n);
    vector<int> vr(row.begin(), row.end());
    vector<int> vl(col.begin(), col.end());
    sort(vr.begin(), vr.end());
    sort(vl.begin(), vl.end());
    int maxr = 0;
    int maxl = 0;
    for(int i=0;i<vr.size()-1;i++) maxr = max(maxr, vr[i+1] - vr[i]);
    for(int i=0;i<vl.size()-1;i++) maxl = max(maxl, vl[i+1] - vl[i]);
    cout<<maxr * maxl<<endl;
    return 0;
}

다른 풀이

#include <stdio.h>
#include <algorithm>
using namespace std;
int x[101];
int y[101];
int main()
{
	int a, b = 0;
	scanf("%d %d", &a, &b);
	int n = 0;
	scanf("%d", &n);
	int k1 = 0;
	int k2 = 0;
	for (int i = 0; i < n; i++)
	{
		int q, w = 0;
		scanf("%d %d", &q, &w);
		if (q == 0)
		{
			x[k1] = w;
			k1++;
		}
		else
		{
			y[k2] = w;
			k2++;
		}
	}
	sort(x, x + k1);
	int max1 = 0;
	if (x[0] > max1)
		max1 = x[0];
	for (int i = 1; i < k1; i++)
	{
		if (x[i] - x[i - 1] > max1)
			max1 = x[i] - x[i - 1];
	}
	if (b - x[k1 - 1] > max1)
		max1 = b - x[k1 - 1];
	//printf("%d\n", max1);

	sort(y, y + k2);
	int max2 = 0;
	if (y[0] > max2)
		max2 = y[0];
	for (int i = 1; i < k2; i++)
	{
		if (y[i] - y[i - 1] > max2)
			max2 = y[i] - y[i - 1];
	}
	if (a - y[k2 - 1] > max2)
		max2 = a - y[k2 - 1];

	printf("%d", max1 * max2);
	return 0;
}

배울 점

• 같은 방법으로 풀이가 진행되었다.