sw expert 1245번 문제

어떻게 풀어야할까 고민했지만 쉽게 떠오르지 않아 결국 검색..

이분탐색을 이용해야 함 

처음에 왼쪽 오른쪽을 어떻게 정해야하나 했는데 그냥 i와 i+1이 있으면 i가 왼쪽 i+1이 오른쪽

물체는 두개 중간에 있다고 생각하면 되는듯 

그래서 이걸 두개씩 계속 호출하면 됨 

 

-처음에는 float형을 썼었는데 이거보고 double 로 고침

오차범위가 줄어든다고 한다.

https://www.acmicpc.net/blog/view/37

부동소숫점 오류

하지만 stack overflow가 일어날 수도 있기에 돌리는 횟수를 제한해야함

1)한 블로그에서는 100번만 돌게했고

2)다른 블로그에서는 int가 대충 1e9정도이므로 이것을 토대로 계산했을 때 오차가 1e-9 미만이어야 한다는 것은 계산 범위가 1e18과 같다는 것이므로 루프를 60번은 돌아야 한다

이런식으로 함

2)번이 더 적게 도니까 60번으로 하도록 하겠음 -50번도 되긴 한다고 함

 

-이분탐색

1.이분 탐색을 하고자 할 때 이미 정렬이 되어있어야 합니다.

2. left, right로 미드값을 잡아줍니다.

3. mid 값과 구하고자 하는 값을 비교 합니다.

4. 비교할시 mid 값보다 구하고자 하는 값이 높으면 left를 mid+1로 만들어주고 낮으면 right를 mid-1로 만들어 줍니다. 

5. left > right 가 될때까지 1~3번을 반복해서 구하고자 하는 값을 찾습니다.

출처: https://wootool.tistory.com/62 [우투리와툴툴]

#include

using std::cout;
using std::cin;
using std::endl;
using std::fixed;

float solve(int depth,float center, float left, float right) {

}

int main(void) {
int testcase_num = 0;
int j_num = 0;
double result = 0;
double x[10] = { 0 };
double mass[10] = { 0 };

cin >> testcase_num;
for (int i = 0;i < testcase_num;i++) {
cin >> j_num;
for (int j = 0;j <j_num; j++) 
cin >> x[j];
for (int j = 0;j <j_num; j++)
cin >> mass[j];
cout << "#" << i + 1 << " ";
for (int i = 0;i < j_num - 1;i++) {
solve(0,(x[i] + x[i + 1] / 2), x[i],x[i+1]);
cout << fixed;
cout.precision(10);
}
cout << endl;
}
return 0;
}

 

우선 여기까지

//이해가 잘 안가서 이분탐색 먼저 다시한번보고 스스로 다시한번 짜봐야겠다

#include
#include

using std::cout;
using std::cin;
using std::endl;
using std::fixed;
double x[10] = { 0 };
double mass[10] = { 0 };


int main(void) {
int testcase_num = 0;
int j_num = 0;
double result = 0;
double left, right, middle;
double s;

cin >> testcase_num;
for (int i = 0;i < testcase_num;i++) {
cin >> j_num;
for (int j = 0;j <j_num; j++) 
cin >> x[j];
for (int j = 0;j <j_num; j++)
cin >> mass[j];
cout << "#" << i + 1 << " ";
for (int i = 0;i < j_num - 1;i++) {
left = x[i], right = x[i + 1];
result = 0;
for (int k = 0;k < 50;k++) {
middle = (left + right) / 2;
s = 0;
for(int j=0;j<=i;j++)
s+=mass[j]/((middle-x[j])*(middle - x[j]));
for (int j = i + 1; j < j_num; ++j)
s -= mass[j] / ((middle - x[j])*(middle - x[j]));
if (s > 0) {
left = middle;
}
else {
result = middle;
right = middle;
}
}
cout << fixed;
cout.precision(10);
}
cout << endl;
}
return 0;
}

 

Resolve함수 하려던건 뺌 j_num을 그때그때 사용해야해서 그냥 빼고 한번에 써버림

어차피 함수써도 안에서 포문도니까 중첩되는건 마\찬가지