Time Limit: 1000msMemory Limit: 262144KB
설명
세종대왕은 현수에게 현수가 다스릴 수 있는 영지를 하사하기로 했습니다. 전체 땅은 사각형으로 표시되고, 그 일부인 정사각형의 땅을 하사합니다.
그 사각형의 땅 중에서 세종대왕이 현수가 다스릴 수 있는 땅의 크기(정사각형 한 변의 길이)를 정해주면 전체 땅 중에서 그 크기의 땅의 위치를 현수가 정하면 되는 것입니다.
정사각형의 땅은 가로, 세로가 x축, y축과 수평을 이루어야 합니다.
체 땅은 2차원 평면좌표 형태로 표현됩니다. 전체 땅 안에는 많은 오렌지 나무가 심겨져 있다. 각 오렌지 나무는 아래 그림처럼 좌표로 표현됩니다.
좌표는 0과 양의 정수로만 표현됩니다.
현수는 오렌지를 무척 좋아하여 오렌지 나무가 가장 많이 포함되는 지역을 선택하고 싶어 합니다. 정사각형 경계선(모서리)에 있는 오렌지 나무도 포함합니다.
현수가 얻을 수 있는 영지의 오렌지 나무 최대 개수를 출력하는 프로그램을 작성하세요. 아래 그림과 같은 땅의 정보가 주어지고,
현수가 하사받을 땅의 크기인 정사각형 한 변의 길이가 3이라면 현수가 얻을 수 있는 최대 오렌지 나무의 개수는 5입니다.
입력
첫 줄에 전체 땅의 크기를 나태내는 W(가로길이)와 H(세로길이), T, S가 입력됩니다.
T는 오렌지 나무의 개수이고, S는 현수가 선택할 수 있는 영지의 크기를 나타내는 정사각형 한 변의 길이입니다.
(3<=W, H<=100,000) (1<=T<=100) (1<=S<=W, H)
두 번째 줄부터 T개의 오렌지 나무 위치 정보가 주어집니다.
출력
첫 번째 줄에 현수가 얻을 수 있는 오렌지 나무의 최대 개수를 출력하세요.
예제 입력
10 9 8 3
3 4
6 3
5 7
6 6
9 5
6 9
7 8
8 9예제 출력
5실패 1 : 시간 초과 및 메모리 초과
#include <iostream>
#include <vector>
#include <algorithm>
// 메모리 및 시간 초과
using namespace std;
void calculateQuadrant(int y, int x, int quard);
void calculateOrnageTree();
int W, H, T, S;
int maxOrange = INT_MIN;
vector<vector<bool>> pos;
vector<pair<int, int>> orangePos;
int main(void)
{
cin >> W >> H >> T >> S;
pos.resize(H + 1, vector<bool>(W + 1, false));
for (int i = 0; i < T; i++)
{
int tmpOrangePosX, tmpOrangePosY;
cin >> tmpOrangePosX >> tmpOrangePosY;
pos[tmpOrangePosY][tmpOrangePosX] = true;
pair<int, int> tmpOrange;
tmpOrange.first = tmpOrangePosX;
tmpOrange.second = tmpOrangePosY;
orangePos.push_back(tmpOrange);
}
calculateOrnageTree();
cout << maxOrange;
}
void calculateOrnageTree()
{
// 특정 오렌지 나무를 기준으로, 그 나무 기준으로 각 4분면을 체크
// 거기서 오렌지 나무가 가장 많은걸 max로 두고 갱신하는걸 반복
for (int i = 0; i < T; i++)
{
for (auto it = orangePos.begin(); it != orangePos.end(); ++it)
{
calculateQuadrant(it->second, it->first, 1);
calculateQuadrant(it->second, it->first, 2);
calculateQuadrant(it->second, it->first, 3);
calculateQuadrant(it->second, it->first, 4);
}
}
}
void calculateQuadrant(int y, int x, int quard)
{
int count = 0;
int posX = S;
int posY = S;
switch (quard)
{
case 1:
posY = (S + y) > H ? H : S + y;
posX = (S + x) > W ? W : S + x;
for (int i = y; i <= posY; i++)
{
for (int j = x; j <= posX; j++)
{
if (pos[i][j]) count++;
}
}
break;
case 2:
posY = (S + y) > H ? H : S + y;
posX = (x - S) < 0 ? 0 : x - S;
for (int i = y; i <= posY; i++)
{
for (int j = posX; j <= x; j++)
{
if (pos[i][j]) count++;
}
}
break;
case 3:
posY = (y - S) < 0 ? 0 : y - S;
posX = (x - S) < 0 ? 0 : x - S;
for (int i = posY; i <= y; i++)
{
for (int j = posX; j <= x; j++)
{
if (pos[i][j]) count++;
}
}
break;
case 4:
posY = (y - S) < 0 ? 0 : y - S;
posX = (S + x) > W ? W : S + x;
for (int i = posY; i <= y; i++)
{
for (int j = x; j <= posX; j++)
{
if (pos[i][j]) count++;
}
}
break;
default:
break;
}
if (count > maxOrange) maxOrange = count;
}실패 2 : 테스트 케이스 통과 실패
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
// 테스트 케이스 실패
using namespace std;
int W, H, T, S;
int maxOrange = INT_MIN;
vector<pair<int, int>> orangePos;
void calculateMaxOrangeTree(pair<int, int> minPos, pair<int, int> maxPos);
void getMinMaxPos(int x, int y, int quart);
int main(void)
{
cin >> W >> H >> T >> S;
for (int i = 0; i < T; i++)
{
int tmpOrangePosX, tmpOrangePosY;
cin >> tmpOrangePosX >> tmpOrangePosY;
pair<int, int> tmpOrange;
tmpOrange.first = tmpOrangePosX;
tmpOrange.second = tmpOrangePosY;
orangePos.push_back(tmpOrange);
}
sort(orangePos.begin(), orangePos.end());
for (auto it = orangePos.begin(); it != orangePos.end(); ++it)
{
getMinMaxPos(it->first, it->second, 1);
getMinMaxPos(it->first, it->second, 2);
getMinMaxPos(it->first, it->second, 3);
getMinMaxPos(it->first, it->second, 4);
}
cout << maxOrange;
}
void getMinMaxPos(int x, int y, int quart)
{
int posX = 0, posY = 0;
int minPosX, minPosY, maxPosX, maxPosY;
pair<int, int> minPos = make_pair(0, 0);
pair<int, int> maxPos = make_pair(0, 0);
switch (quart)
{
case 1:
minPosX = x;
minPosY = y;
maxPosX = (S + x) > W ? W : S + x;
maxPosY = (S + y) > H ? H : S + y;
break;
case 2:
minPosX = (x - S) < 0 ? 0 : x - S;
minPosY = y;
maxPosX = x;
maxPosY = (S + y) > H ? H : S + y;
break;
case 3:
minPosX = (x - S) < 0 ? 0 : x - S;
minPosY = (y - S) < 0 ? 0 : y - S;
maxPosX = x;
maxPosY = y;
break;
case 4:
minPosX = x;
minPosY = (y - S) < 0 ? 0 : y - S;
maxPosX = (S + x) > W ? W : S + x;
maxPosY = y;
break;
default:
break;
}
minPos.first = minPosX;
minPos.second = minPosY;
maxPos.first = maxPosX;
maxPos.second = maxPosY;
calculateMaxOrangeTree(minPos, maxPos);
}
void calculateMaxOrangeTree(pair<int, int> minPos, pair<int, int> maxPos)
{
int count = 0;
for (auto it = orangePos.begin(); it != orangePos.end(); ++it)
{
if (it->first > maxPos.first) break;
if (it->first >= minPos.first && it->first <= maxPos.first)
if (it->second >= minPos.second && it->second <= maxPos.second)
count++;
}
if (count > maxOrange) maxOrange = count;
}처음 아이디어는, 각 오렌지 나무를 '대각선 끝 점'으로 가정하고 이 점을 기준으로 사분면을 쪼개어 만들어 네모를 치면 '포함'하는 오렌지 나무가 많을거라 생각했다. 처음에는 시간과 메모리 초과로 틀렸다고 하여 개선한 두번째에서도 틀렸을때 머리가 멍해졌다. 아니, 어쩌라는걸까.
생각을 좀 해봤다. 좀 많이 해봤다. 다음의 경우는, 이 알고리즘이 해결하지 못했다.
마름모, 마름모가 문제였다. 다음과 같이
마름모 모양인 경우, 내가 원래 구현했던 '꼭짓점'을 기준으로 한다면 아래처럼 최대 3개밖에 커버를 못친다.
그럼 도대체 어떻게 해야할까? 애초에, 지금 짠 코드는 너무 더럽다. 너무 뭐가 많고 지저분하다. 천천히, 수학적으로 접근해보자. 다음과 같이 상자가 하나 있다고 가정해보자.
상자가 '모든 오렌지의 x값 중 최소 값'으로 쓱 이동하면, 오렌지는 포함되면 포함됐지 나가지 않는다. 반대로 Y도 마찬가지다. 즉, 모든 X와 Y값을 가지고 그 중 최소값 기준으로 상자를 만들기 시작해서 오른쪽 위로 상자를 만들어 나가는 행위를 모든 오렌지에 적용 시키면 그 중에서 반드시 오렌지를 가장 많이 담는 상자가 생성된다.
그럼 시작점을 무조건 (0, 0)으로 잡아야할까? 아니다. 모든 오렌지들의 X와 Y를 받아서, 이 중 가장 작은 것들로 '임의의 점'을 만든다. 그리고 이 점에서 먼저 사각형을 만들고 오렌지 개수를 체크, 이렇게 모든 오렌지 좌표에 대해 X와 Y 좌표를 작은것부터 받아와서 오렌지가 몇개나 포함되어있는지 체크, 즉 2차원 Brute-Force 문제인 것이다. 내부의 오렌지의 개수만 순회하며 해당 오렌지가 최대 좌표값보다 작고, 최소 좌표값보다 큰지만 검사하면 되는 간단한...문제였다.
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
int answer = INT_MIN;
int W, H, T, S;
vector<pair<int, int>> orangePos;
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> W >> H >> T >> S;
for (int i = 0; i < T; i++)
{
pair<int, int> tmpOrange;
cin >> tmpOrange.first >> tmpOrange.second;
orangePos.push_back(tmpOrange);
}
sort(orangePos.begin(), orangePos.end());
for (int i = 0; i < T; i++)
{
for (int j = 0; j < T; j++)
{
int minX = orangePos[i].first;
int minY = orangePos[j].second;
int maxX = minX + S;
int maxY = minY + S;
int count = 0;
for (int k = 0; k < T; k++)
{
if (orangePos[k].first >= minX && orangePos[k].first <= maxX &&
orangePos[k].second >= minY && orangePos[k].second <= maxY)
count++;
}
if (count > answer) answer = count;
}
}
cout << answer;
return 0;
}