문제 링크

문제

한 변의 길이가 1cm인 정사각형 모양의 타일이 있다. 이 타일들이 큰 정사각형을 빈틈없이 채우고 있는데, 정사각형의 한 변의 길이는 짝수이다. 이 한 변의 길이를 Ncm이라고 하자.

큰 정사각형에 접하는 원을 그린다. 정사각형을 이루고 있는 N×N개의 타일 중에는 원의 둘레가 그려진 타일도 있고, 그렇지 않은 타일도 있게 된다. 원의 둘레가 그려져 있는 타일의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 짝수 N(2 ≤ N ≤ 150,000,000)이 주어진다.

출력

첫째 줄에 원의 둘레가 그려진 타일의 개수를 출력한다.

접근 과정

  1. 그래프를 그려주는 사이트에 가서 원 그래프를 그려보았다. N이 항상 짝수이기 때문에 각 사분면이 동일한 갯수의 타일의 원의 둘레가 그려지므로 한 사분면에서 원이 그려지는 타일의 갯수를 파악한 뒤 4를 곱해주기로 하였다.
  2. 1사분면에서 가장 왼쪽 아래 타일을 (1, 1)로 두었을 때(점의 좌표와 블럭의 좌표는 별개) 원점에서 좌측 하단 점 까지의 길이가 반지름 보다 짧고 우측 상단 까지의 길이가 반지름 보다 길면 원이 그려지므로 이를 통해 타일이 주어지면 원이 그려질 수 있는지 확인하는 함수를 작성하였다. * hasCircumference(x, y) *
  3. N의 최대치가 작지 않으니 한 사분면에 대해 완전 탐색하지 않고 별도로 탐색 경로를 따로 정해주었다. 원이 시작되는 꼭지점에서 끝나는 꼭지점을 향해 탐색하는 방향으로 탐색하는 식이다. 다른 사람들의 풀이들 또한 각자 나름대로의 탐색 방법을 사용하고 있었다.

소스 코드

#include <iostream>
using namespace std;

long long radiusSquare;

bool hasCircumference(long long x, long long y) {
    return (x - 1) * (x - 1) + (y - 1) * (y - 1) < radiusSquare
            && x * x + y * y > radiusSquare;
}

int main(void) {
    int N, radius;

    cin >> N;
    radius = N / 2;
    radiusSquare = (long long)radius * radius;
    
    unsigned int cnt = 0;
    int xBase = 1;
    for (int y = radius; y >= 0; --y) {
        for (int x = xBase; x <= radius; ++x) {
            if (hasCircumference(x, y)) {
                ++cnt;
                xBase = x;
            } else {
                if (x != xBase) {
                    xBase = x - 1;
                    break;
                }
            }
        }
    }

    cout << cnt * 4 << endl;
    return 0;
}