BOJ 3412 - Darts

문제

BOJ 3412 - Darts

다트 게임에서 n개의 다트를 던진 좌표 (x, y)가 주어질 때, 총 점수를 계산하는 문제이다.

과녁은 중심에서 동심원으로 10개의 구역으로 나뉜다:

• j번째 구역의 반지름: 20 * j
• j번째 구역의 점수: 11 - j (j = 1이 가장 안쪽, 점수 10)
• 반지름 200 초과이면 점수 0

다트의 중심으로부터의 거리는 피타고라스 정리로 계산한다: dist = x^2 + y^2

입력

• 첫 번째 줄에 테스트케이스 수 T가 주어진다.
• 각 테스트케이스의 첫 줄에 다트 수 n이 주어진다.
• 다음 n개의 줄에 각 다트의 좌표 x, y가 주어진다.

출력

각 테스트케이스마다 총 점수를 출력한다.

예제

풀이

각 다트의 좌표에서 중심까지의 거리를 계산하고, 해당 구역의 점수를 누적하는 기하학 구현 문제이다.

1. T개의 테스트케이스를 처리한다.
2. n개의 다트 좌표를 입력받는다.
3. 각 좌표에서 거리의 제곱 dist = x^2 + y^2을 계산한다.
4. j를 1부터 10까지 증가시키며 dist <= (20 * j)^2인 최소 j를 찾는다.
5. 해당 j의 점수 11 - j를 합산한다.
6. 반지름 200 초과이면 점수 0이므로 루프가 끝날 때까지 조건이 맞지 않으면 자동으로 0점 처리된다.

핵심 아이디어: 거리 비교 시 제곱근 계산 없이 거리의 제곱과 반지름의 제곱을 직접 비교한다 (dist <= pow(20*j, 2)). 이로써 부동소수점 오차를 최소화하면서 효율적으로 구역을 판별한다.

코드

#include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  int T;
  cin >> T;
  for (int t = 0; t < T; t++)
  {
    int n;
    cin >> n;
    double total = 0;
    for (int i = 0; i < n; i++)
    {
      double x, y;
      cin >> x >> y;
      double dist = x * x + y * y;
      for (int j = 1; j <= 10; j++)
      {
        if (dist <= pow(20 * j, 2))
        {
          total += 11 - j;
          break;
        }
      }
    }
    cout << (int)total << "\n";
  }
  return 0;
}

복잡도

• 시간: O(T * N) - 테스트케이스 T, 다트 수 N에 비례 (구역 판별은 최대 10번으로 상수)
• 공간: O(1) - 추가 메모리 불필요