[Softeer] 사물인식 최소 면적 산출 프로그램

https://softeer.ai/practice/info.do?idx=1&eid=531&sw_prbl_sbms_sn=120490 

Softeer

 

시간제한은 C++ 기준 2초이고,

제일 먼저 봤을 때 생각나는 간단한(브루트포스) 풀이는

모든 색깔의 점을 하나씩 골라서 푸는 것 이었는데,

 

문제를 읽어보면 알겠지만 점의 개수 N은 최대 100이고,

점 색깔의 개수 K는 최대 20이다.

 

그러면 최악의 경우, 1~20의 색깔에 100개의 점이 5개씩 퍼져있을 수 있는데,

이 경우 구해야 하는 경우의 수는 5^20 이다.

 

5^20을 계산기에 두들겨봤는데 생각보다 너무 큰 숫자라서.. 2초는 정말 택도없겠다 싶었다

그래서 점을 선택하는 것이 아닌

2000*2000으로 되어있는 영역을 선택하는 방법으로 접근해보려 했는데

이 경우도 시간복잡도가 말이 안 되길래...

 

어쩌지... 만 하고 있었는데 소프티어 해설 페이지에서 보니까 맨 처음 생각한 풀이로 풀면 된다고 하신다

정확하게는, 맨 처음 풀이로 풀되 가지치기를 넣는 것이 정답

 

음.... 근데 이게 가지치기라는게 테스트 케이스가 가지치기가 전혀 적용되지 않게 주어진다면

의미 없는 거인데.. 시간복잡도는 원래 최악의 경우를 가지고 계산하는 거니까

 

시험에서도 이런 문제가 나오면 그냥 시간복잡도 안된다고 다른 방법만 고려하면서

시간을 낭비해 결국 못 풀 거 같아서 무서웠다

 

암튼 그래서 기억해놓으려고 저장을 해놓음

 

코드가 없으면 심심하니까 코드도..

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

using namespace std;

int N, K;
int min_area = 5000000;
vector<pair<int, int>> point[21];

void dfs(int color, int si, int ei, int sj, int ej) {
	if(color == K+1) {
		int area = abs(si-ei)*abs(sj-ej);
		//printf("area: %d\n", area);
		min_area = min(min_area, area);
		return;
	}

	for(int i = 0; i<point[color].size(); i++) {
		//printf("color %d -> %d번째\n", color, i);
		int ni = point[color][i].first;
		int nj = point[color][i].second;

		int tmp = abs(min(si, ni)-max(ei, ni))*abs(min(sj, nj)-max(ej, nj));
		if(tmp >= min_area) {
			//printf("tmp: %d -> 선택안함\n", tmp);
			continue;
		}
		//printf("->선택 dfs(%d, %d, %d, %d, %d)\n", color + 1, min(si, ni), max(ei, ni), min(sj, nj), max(ej, nj));
		dfs(color + 1, min(si, ni), max(ei, ni), min(sj, nj), max(ej, nj));
	}
}

int main(int argc, char** argv)
{
	
	scanf("%d%d", &N, &K);
	int x, y, c;
	for(int i = 0; i<N; i++) {
		scanf("%d%d%d",&x, &y, &c);
		point[c].push_back({x, y});
	}
	dfs(1, 1001, -1001, 1001, -1001);
	printf("%d", min_area);
	return 0;
}