[Softeer] 사물인식 최소 면적 산출 프로그램
Date:
[Softeer] 사물인식 최소 면적 산출 프로그램
Problem URL : 사물인식 최소 면적 산출 프로그램
통과 코드
#include <iostream>
#include <vector>
using namespace std;
int n, k;
int ans;
vector<vector<pair<int,int>>> points;
void dfs(int cnt, int minX, int maxX, int minY, int maxY) {
if(cnt == k) {
int area = (maxX - minX) * (maxY - minY);
if(ans > area) {
ans = area;
}
return;
}
for(int i = 0; i < points[cnt].size(); i++) {
int x = points[cnt][i].first;
int y = points[cnt][i].second;
int minX2 = minX; int maxX2 = maxX; int minY2 = minY; int maxY2 = maxY;
if(minX > x) minX2 = x;
if(maxX < x) maxX2 = x;
if(minY > y) minY2 = y;
if(maxY < y) maxY2 = y;
int area = (maxX2 - minX2) * (maxY2 - minY2);
if(ans <= area) {
continue; // [1]
}
dfs(cnt + 1, minX2, maxX2, minY2, maxY2);
}
}
int main(int argc, char** argv)
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> k;
ans = 1e9;
points.resize(k);
int x, y, z;
for(int i = 0; i < n; i++) {
cin >> x >> y >> z;
points[z - 1].push_back({x,y});
}
dfs(0,1e9,-1e9,1e9,-1e9);
cout << ans << endl;
return 0;
}
시간 초과 풀이(n <= 40까지 통과)
#include <iostream>
#include <vector>
using namespace std;
int n, k;
int ans;
vector<vector<pair<int,int>>> points;
void dfs(int cnt, vector<pair<int,int>> &pick) {
if(cnt == k) {
int minX = 1e9; int maxX = -1e9; int minY = 1e9; int maxY = -1e9;
for(int i = 0; i < k; i++) {
int x = pick[i].first;
int y = pick[i].second;
if(minX > x) minX = x;
if(maxX < x) maxX = x;
if(minY > y) minY = y;
if(maxY < y) maxY = y;
}
int area = (maxX - minX) * (maxY - minY);
if(ans > area) {
ans = area;
}
return;
}
for(int i = 0; i < points[cnt].size(); i++) {
pick.push_back(points[cnt][i]);
dfs(cnt + 1, pick);
pick.pop_back();
}
}
using namespace std;
int main(int argc, char** argv)
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> k;
ans = 1e9;
points.resize(k);
int x, y, z;
for(int i = 0; i < n; i++) {
cin >> x >> y >> z;
points[z - 1].push_back({x,y});
}
vector<pair<int, int>> pick;
dfs(0,pick);
cout << ans;
return 0;
}
투 포인터 풀이(아직 시간초과… ㅠㅠ)
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int sum[21][2002][2002];
struct Point {
int x;
int y;
int color;
Point(int _x, int _y, int _color) : x(_x), y(_y), color(_color) {};
};
int main(int argc, char** argv) {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k;
int ans = 1e9;
cin >> n >> k;
int x, y, z;
int minX = 1e9;
int maxX = 0;
int minY = 1e9;
int maxY = 0;
vector<Point> points;
for (int i = 0; i < n; i++) {
cin >> x >> y >> z;
if (minX > x + 1001) minX = x + 1001;
if (maxX < x + 1001) maxX = x + 1001;
if (minY > y + 1001) minY = y + 1001;
if (maxY < y + 1001) maxY = y + 1001;
points.push_back(Point(x,y,z));
}
for (int i = 0; i < n; i++) {
int x = points[i].x;
int y = points[i].y;
int z = points[i].color;
for (int j = x + 1001; j <= maxX; j++) {
sum[z][j][y + 1001] += 1; // y행의 구간합을 기록
}
}
for (int i = minX; i < maxX; i++) {
for (int j = i + 1; j <= maxX; j++) {
map<int, int> m;
int start = minY;
int end = minY;
int a = minY;
int b = maxY;
for (int color = 1; color <= k; color++) {
int tmp = sum[color][j][minY] - sum[color][i - 1][minY];
if (tmp != 0) m[color] += tmp;
}
bool check = false;
while (start <= end) {
if (m.size() == k) {
check = true;
if (b - a > end - start) {
b = end;
a = start;
}
for (int color = 1; color <= k; color++) {
int tmp = sum[color][j][start] - sum[color][i - 1][start];
if (tmp != 0) m[color] -= tmp;
if (m[color] == 0) {
m.erase(color);
}
}
start++;
} else {
end++;
if (end == maxY + 1) {
break;
}
for (int color = 1; color <= k; color++) {
int tmp = sum[color][j][end] - sum[color][i - 1][end];
if (tmp != 0) m[color] += tmp;
}
}
}
int area = (b - a) * (j - i);
if (ans > area && check) {
ans = area;
}
}
}
if (ans == 1e9) {
ans = 0;
}
cout << ans << endl;
return 0;
}
투 포인터 정해
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m;
vector<pair<pair<int, int>, int>> points;
vector<pair<int, int>> v;
int color[30];
int main()
{
int i, j, k;
int a, b, c;
int s, e;
int cnt;
int ans = 1000000000;
cin >> n >> m;
for(i = 0; i < n; i++)
{
cin >> a >> b >> c;
points.push_back(make_pair(make_pair(a, b), c));
}
sort(points.begin(), points.end());
for(i = 0; i < n; i++)
{
v.clear();
for(j = i; j < n; j++)
{
v.push_back(make_pair(points[j].first.second, points[j].second));
sort(v.begin(), v.end());
memset(color, 0, sizeof(color));
cnt = 1;
color[v[0].second] = 1;
s = 0;
e = 0;
while(e < v.size())
{
if(cnt == m)
{
ans = min(ans, (points[j].first.first - points[i].first.first) * (v[e].first - v[s].first));
color[v[s].second]--;
if(!color[v[s].second]) cnt--;
s++;
}
else
{
e++;
if(e == v.size()) break;
color[v[e].second]++;
if(color[v[e].second] == 1) cnt++;
}
}
}
}
cout << ans << '\n';
}
Comments
두번째 풀이(시간 초과)에서, 조기 종료 할 수 있는 조건([1])을 넣었더니 통과가 되었다.
세번째 풀이는 2D 투포인터 알고리즘을 적용해보았는데 테캐는 통과하고 시간 초과가 떴다.
투 포인터로 푸신 분께서 정해를 가르쳐주셨다! map을 쓰지 않고 color 배열과 변수 cnt만으로 포함한 색깔을 기록해주었다.
그리고 int sum[21][2002][2002] 과 같은 무식하게 큰 배열도 필요없었다…
반성하고 투 포인터 풀이 제대로 익혀두자!
댓글