해당 문제는 SW Expert Academy의 문제로, 개인학습을 목적으로 게시합니다.

Problem

보드에 그려진 다트 게임을 생각해보자. 보드에는 중심이 원점이고 반지름이 20,40,60,80,100,120,140,160,180,200 (단위는 mm)인 10개의 원이 그려져 있다.
각각의 화살은 꽂힌 지점을 감싸는 가장 가까운 원(경계선에 꽂힌 경우도 포함)의 반지름이 20 * (11 - p)인 경우 p점을 획득한다. (1 ≤ p ≤ 10)
만약 가장 큰 원 바깥에 꽂혔다면 얻는 점수는 없다. N 개의 화살을 던진 위치가 주어지면, 총 몇 점을 얻었는지 계산하자.

[입력]
첫 번째 줄에 테스트 케이스의 수 TC가 주어진다. 이후 TC개의 테스트 케이스가 새 줄로 구분되어 주어진다.
각 테스트 케이스는 다음과 같이 구성되었다.
- 첫 번째 정수는 화살의 개수 N이다. (1 ≤ N ≤ 1000000)
- 이후 화살이 떨어진 위치 (x, y) 가 두 정수로 주어진다. (-200 ≤ x, y ≤ 200)

[출력]

각 테스트 케이스마다 점수의 합을 출력하라.

Approach

보드는 원판이고, 중심이 (0,0)인 좌표계로 설명할 수 있습니다. 다트의 위치는 (x,y)의 좌표로 주어집니다. 우리가 이 정보로 알 수 있는 것은 다음과 같습니다.

$\begin{cases}distance:원점과\;다트간의\;거리\\ radius: 다트를\;감싸는\;가장\;가까운\;원의\;반지름\end{cases}$

가장 먼저 구해야 하는 것은$distance$입니다. 원점에서 특정 좌표의 위치는 다음 식으로 구할 수 있습니다.

여기서 $distance$를 이용하여 $radius$를 알아내는 것이 이 문제 풀이의 핵심입니다.

주어진 점수를 구하는 공식은 $score$에 관한 함수이기 때문에 $radius$에 관한 함수로 바꾸면 다음과 같습니다.

Caution

1. 거리가 0 이라면 다트를 감싸는 가장 작은 원의 반지름은 20입니다.
2. 거리가 20이라면 다트를 감싸는 가장 작은 원의 반지름은 20입니다.
3. 거리가 20.001이라면 다트를 감싸는 가장 작은 원의 반지름은 40입니다.
4. 거리가 200이라면 다트를 감싸는 가장 작은 원의 반지름은 200입니다.
5. 거리가 200.001이라면 점수는 0점 입니다.

Thinking: sqrt

우선 제곱근을 구할 필요가 있습니다. 헤더파일을 사용하지 않고 수치적으로(numerically) 제곱근을 근사하는 방법을 이용하여 제곱근을 구합니다.

inline float sqrt(int k){
    float x = k;
    for(int i=0; i < 12; i++)
        x = 0.5*(x+k/x);
    return x;
}

정수부를 20으로 떨어지게 만들어준 다음 공식을 적용한 알고리즘을 사용하여 코드를 짰습니다.
결론적으로 Fail 코드이기 때문에 자세히 설명하지 않겠습니다.

#include<iostream>
using namespace std;
 
inline float sqrt(int k){
    float x = k;
    for(int i=0; i <12; i++){
        x = 0.5*(x+k/x);
    }
    return x;
}
     
int main(int argc, char** argv)
{
    int test_case;
    int T, N, x, y, p;
    //freopen("input.txt", "r", stdin);
    scanf("%d", &T);
    for(test_case = 1; test_case <= T; ++test_case)
    {
        int score = 0;
        cin >> N;
        for(int i = 0; i < N; i++){
            scanf("%d %d", &x, &y);
            float dist = sqrt(x*x+y*y);
            p = dist-(int)dist%20;
            p += dist-(int)dist>0? 20:0;
            score += 11-p/20;
        }
        printf("#%d %d\n",test_case, score);
    }
    return 0;
}

Conclusion: sqrt가 없는 거리 측정

시간 초과가 발생하여 Fail하여 sqrt의 함수 구현에 문제가 있지 않을까 하여 공용체 메모리를 이용한 sqrt 함수도 구현하여 사용하여 보았지만 모두 Fail하였습니다.
그 말인 즉슨, 직접 구현해보면 sqrt 함수가 생각보다 연산량을 잡아먹는 함수임을 알 수 있기 때문에 sqrt 자체를 사용하지 않는 방법을 고려하여야 합니다.

사실 거리를 정확히 mm 단위로 나타낼 필요는 없습니다. 그저 몇 점인지 아는 것이 중요하기 때문에 다음과 같이 계산하여도 문제가 없습니다.

이렇게 하면 제곱근에서 한번 곱하는 것으로 연산량을 줄일 수 있습니다.

for문으로 돌면서 점수를 체크하여도 전보다 연산량이 줄고 정확도는 높아졌기 때문에(부동 소수점 자료가 없기 때문) 더욱 정확하고 빠르게 연산이 가능합니다.

#include<iostream>
using namespace std;
     
int main(int argc, char** argv){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int test_case, T, N, x, y, score, i, d, d2;
    cin >> T;
    for(test_case = 1; test_case <= T; ++test_case)
    {
        score = 0;
        cin >> N;
        for(i = 0; i < N; i++){
            cin >> x >> y;
            d2= x*x+y*y;
             
            for(d = 20; d<=200; d+=20)
                if(d*d >= d2)
                    break;
            score += 11-d/20;
        }
        cout << '#' << test_case << ' ' << score << '\n';
    }
    return 0;
}