글 읽기 - 카카오 코드 페스티벌 예선) 캠핑 문제 질문입니다.(절박..)

aung 6년 전 0

질문을 하고싶어도 질문할 곳이 없어서 BOJ 에 올리는 점 죄송합니다.. 넓은 아량으로 이해 바랍니다 ㅠ.ㅠ

카카오에서 올려준 풀이와 동일하게

sum[i][j]: x좌표가 [0, (x좌표 중 i번째로 작은 값)], y좌표가 [0, (y좌표 중 j번째로 작은 값)]인 쐐기의 개수

라고 생각해서 N^2으로 모든 경우에 대해서 내부의 쐐기 개수가 0인 경우만 카운트해서 정답을 출력했는데

계속 틀렸다고 나옵니다. 많은 시간 투자해보았지만 제 능력으로는 어디가 문제인지 잘 모르겠습니다..

저에게 도움을 주시면 감사하겠습니다 ㅠㅠ..

이건 문제 링크입니다!

https://programmers.co.kr/lear...

#include <vector>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long int LLi;

int X, Y;
int cnt, sum[5005][5005];
vector<int> xs, ys;
int cul(int i, int j, int fx, int fy) { 
	int val = 0;
	val += (i >= fx) ? sum[i - fx][j] : 0;
	val += (j >= fy) ? sum[i][j - fy] : 0;
	val -= (i >= fx && j >= fy) ? sum[i - fx][j - fy] : 0;
	return val;
}

int solution(int N, vector<vector<int>> data) {
	cnt = 0;
	X = 0;
	Y = 0;
	xs.clear(), ys.clear();
	memset(sum, 0, sizeof(sum));
	for (int i = 0; i < N; i++) {
		xs.push_back(data[i][0]);
		ys.push_back(data[i][1]);
	}
	//x 값들 정렬 후 중복 제거
	sort(xs.begin(), xs.end());
	int ref = unique(xs.begin(), xs.end()) - xs.begin();
	if (ref != xs.size()) xs.erase(xs.begin() + ref, xs.end());
	//y 값들 정렬 후 중복 제거
	sort(ys.begin(), ys.end());
	ref = unique(ys.begin(), ys.end()) - ys.begin();
	if (ref != ys.size()) ys.erase(ys.begin() + ref, ys.end());

	for (int i = 0; i < N; i++) {
		data[i][0] = lower_bound(xs.begin(), xs.end(), data[i][0]) - xs.begin();
		data[i][1] = lower_bound(ys.begin(), ys.end(), data[i][1]) - ys.begin();
		sum[data[i][0]][data[i][1]] = 1;
	}
	X = xs.size();
	Y = ys.size();

	//sum 배열 값 채우기
	for (int i = 0; i < X; i++)
		for (int j = 0; j < Y; j++)
			sum[i][j] += cul(i, j, 1, 1);

	//모든 경우에서 내부의 쐐기 개수가 0인 직사각형들 구하기
	for (int i = 0; i < N; i++)
		for (int j = i + 1; j < N; j++){
			//(기저)직사각형이 아닌경우 
			if (data[i][0] == data[j][0] || data[i][1] == data[j][1]) continue;
			//대각에 위치한 두 정점 구하기
			int lx, ly, hx, hy, val;
			lx = min(data[i][0], data[j][0]);
			ly = min(data[i][1], data[j][1]);
			hx = max(data[i][0], data[j][0]);
			hy = max(data[i][1], data[j][1]);
			//그대로 구하면 경계 범위에 있는 쐐기들도 포함하므로 오른쪽 대각선의 정점 값을 x,y값 각각 -1 해준다.
			hx--, hy--;

			//두 정점에서 x 또는 y값들의 차가 1이면 항상 쐐기 개수는 0이므로 카운팅 해준다.
			if (hx == lx || hy == ly) val = 0;
			else val = sum[hx][hy] - cul(hx, hy, hx - lx, hy - ly);
			
			//직사각형 내부에 쐐기가 없는 경우 카운팅
			if (val == 0)
				cnt++;
		}

	return cnt;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

카카오 코드 페스티벌 예선) 캠핑 문제 질문입니다.(절박..)

aung 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말