글 읽기 - 50%에서 틀렸습니다 질문

kookies371 3년 전 0

풀이 방법:

1. 20개의 점을 일단 모두 더해 sum_x, sum_y에 저장

2. 20개의 점 중 10개의 점을 DFS를 이용해 뽑아 sum_x에서 두 번 뺄고, 그 결과를 result에 저장

(여기서 result에 오버플로우가 나는 것을 방지하기 위해 long long 형 사용)

3. result 중 최솟값을 뽑아 최종적으로 sqrt(result)를 출력

검사해본 예시

1. 문제에 나온 예시

2. 0 0 / 1 1 / 2 2 / 3 3 : 0 나오는 것 확인

3. 100000 100000 (10개) / -100000 -100000 (9개) / -99999 -99999 : sqrt(2) 나오는 것 확인

(3번은 '같은 점은 없다'라는 문제의 조건과는 맞지 않지만 점의 갯수가 많을 때 무슨 일이 일어나는지 확인해보기 위한 예시)

무엇이 문제일까요...?

#include <iostream>
#include <vector>
#include <cmath>

#define MAX 9223372036854775807

int t, n, x, y;
int sum_x, sum_y;
long long result;
std::vector<int> xs;
std::vector<int> ys;

void DFS(int sum_x_int, int sum_y_int, int count, int now_index) {
	// basic calculation
	sum_x_int -= 2*xs[now_index];
	sum_y_int -= 2*ys[now_index];
	// base condition
	if (count == n / 2) {
		long long sum_x_long_int = static_cast<long long>(sum_x_int);
		long long sum_y_long_int = static_cast<long long>(sum_y_int);
		result = std::min(result, sum_x_long_int * sum_x_long_int + sum_y_long_int * sum_y_long_int);
	}
	else {
		for (int i = now_index + 1; i < n; i++) {
			DFS(sum_x_int, sum_y_int, ++count, i);
		}
	}
}

int main() {
	std::cin >> t;
	while (t--) {
		// initiate
		sum_x = 0;
		sum_y = 0;
		result = MAX;
		xs.clear();
		ys.clear();
		// input
		std::cin >> n;
		for (int i = 0; i < n; i++) {
			std::cin >> x >> y;
			xs.push_back(x);
			ys.push_back(y);
			sum_x += x;
			sum_y += y;
		}
		// solve
		for (int i = 0; i < n/2; i++) {
			DFS(sum_x, sum_y, 1, i);
		}
		// print
		std::cout << std::fixed;
		std::cout.precision(15);
		std::cout << sqrt(static_cast<double>(result)) << std::endl;
	}

	return 0;
}

1207koo 3년 전 1

25번째 줄: ++count로 for문 돌 때마다 count가 올라가는 것 같습니다.

49번째 줄: i<=n/2로 해야 할 것 같습니다. 시작 위치가 n/2가 가능한 것으로 보입니다.

대충 훑어본 거라 틀릴 수도 있지만 가장 가능성이 높은 두 가지 입니다.

kookies371 3년 전 0

말씀하신 두 부분 수정했더니 맞았습니다!

정말 감사합니다!!

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

문제

문제

출처

ICPC

50%에서 틀렸습니다 질문

kookies371 3년 전 0

1207koo 3년 전 1

kookies371 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말