[백준][C++] 2725: 보이는 점의 개수

문제

2725번: 보이는 점의 개수

풀이

유클리드 호제법, 누적 합

 

[백준][C++] 10166: 관중석

위의 문제처럼 좌표를 기약분수로 표현하여, 중복되지 않았을 때, 답으로 추가하여 구하려고 했지만 시간초과가 발생하였다. 

 

N에서 보이는 점은 N - 1에서 보이는 점을 포함하므로, N에서 보이는 점은 (N - 1에서 보이는 점) + (N에서만 보이는 점)이다. N에서만 보이는 점은 x가 N이거나, y가 N인 줄에서 보이는 점이다. 해당 점에서의 최대공약수가 1이라면, 해당 점은 N - 1까지 가려지지 않은 점이다. 

 

코드

#include <iostream>

using namespace std;

int nums[1001];

int gcd(int a, int b)
{
    if (a < b)
    {
        swap(a, b);
    }

    int temp;
    while (b != 0)
    {
        temp = a % b;
        a = b;
        b = temp;
    }

    return a;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int C;
    cin >> C;

    nums[1] = 3;

    int num = 0;
    for (int i = 2; i <= 1000; ++i)
    {
        // i에서 보이는 점은 i - 1에서 보이는 점을 포함한다.
        nums[i] = nums[i - 1];
        for (int j = 1; j < i; ++j)
        {
            // i, j의 최대공약수가 1이라면 i - 1까지 가려지지 않은 점이다.
            int GCD = gcd(i, j);

            if (GCD == 1)
            {
                // 기울기가 1인 선분과 대칭하므로, 2씩 추가
                nums[i] += 2;
            }
        }
    }

    while (C--)
    {
        int N;
        cin >> N;

        cout << nums[N] << '\n';
    }

    return 0;
}