[백준 2725번] 보이는 점의 개수 (C++)

문제링크 : https://www.acmicpc.net/problem/2725

#include <bits/stdc++.h>
using namespace std;

bool check[1001][1001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int C, N;
    cin >> C;

    check[1][1]=1;
    for(int i=1; i<=1000; i++)
    {
        for(int j=1; j<=1000; j++)
        {
            if(gcd(i, j)==1) check[i][j]=1;
        }
    }

    while(C--)
    {
        cin >> N;
        int result = 2; //(0, 1) (1, 0)은 항상 보이는 점
        for(int i=1; i<=N; i++)
        {
            for(int j=1; j<=N; j++)
            {
                if(check[i][j])  result++;
            }
        }

        cout << result << "\n";
    }

    return 0;
}

 

원점과 좌표의 최대 공약수가 1이라면 겹치는 좌표가 없다는 뜻이다. 

따라서 이를 통해 보이는 점의 개수 카운팅이 가능하다.

먼저 전체 범위에 대해 미리 gcd 계산을 통해 가능한 값을 모두 구하고, 이후에 입력받은 값을 토대로 가능한 경우를 카운팅해준다.

이때 주의할 점은 카운팅하는 변수의 시작 값이 2인데, 이는 원점에서 (0, 1)과 (1, 0)은 항상 보이는 점에 해당하기 때문이다.