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

문제

10166번: 관중석

풀이

수학, 유클리드 호제법

 

좌석을 분수로 생각한다. 반지름이 i이면서 j번째 좌석은 i / j로 표현한다. i1 / j1과 i2 / j2가 기약분수로 표현했을 때, 같은 값을 가진다면, 한 좌석은 다른 좌석을 가리게 된다. 

 

D1부터 D2까지의 좌석을 기약분수로 나타냈을 때, 중복되는 경우 답에 추가하지 않는다.

코드

#include <iostream>

using namespace std;

// 좌석을 분수로 표현
bool nums[2001][2001];

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 D1, D2;
    cin >> D1 >> D2;

    int answer = 0;
    for (int i = D1; i <= D2; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            // i / j를 기약분수로 표현했을 때, 같은 값을 가진다면 가려진다.
            // 이미 i / j가 가려졌다면, answer에 추가하지 않는다.
            int GCD = gcd(i, j);
            int numerator = j / GCD;
            int denominator = i / GCD;
            if (nums[numerator][denominator] == false)
            {
                answer++;
                nums[numerator][denominator] = true;
            }
        }
    }

    cout << answer;

    return 0;
}