백준 10166번 관중석 C++

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

10166번: 관중석

 문제 풀이

 이 문제는 원 위에 정D1각형부터 정D2각형까지 그릴 때 중심에서 다른 점들에 의해 '가려지지 않는' 점들의 개수를 묻는 문제이다. 

 제한시간이 1초이고 D2가 2000이하이므로 넉넉하게 O(n^2)으로 해도 별 문제가 없을 것 같아보인다. 반지름이 D1인 원에서 부터 반지름이 D2인 원까지 각각의 원에 대해서 각각의 좌석들에 대해 모두 탐색을 해보자.

각 원에서 좌석들에 그에 대응하는 분수를 대응시켜보자. 이러면 분수를 기약분수로 나타내었을 때 값이 같은 좌석들끼리는 서로 같은 직선상에 있다는 것을 알 수 있다. 따라서 이를 이용해서 문제를 접근하면, 구하는 값은 등장한 기약분수의 종류이다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int m,int n)
{
    if(m==n)
    {
        return m;
    }
    else if(m>n)
    {
        return gcd(m-n,n);
    }
    return gcd(m,n-m);
}

int D1,D2,c=0;
bool fraction[2001][2001]={false,};
int main()
{
    cin>>D1>>D2;
    for(int i=D1;i<=D2;i++)
    {
        for(int j=1;j<=i;j++)
        {
            if(fraction[j/gcd(i,j)][i/gcd(i,j)])
            {
                continue;
            }
            fraction[j/gcd(i,j)][i/gcd(i,j)] = true;
            c++;
        }
    }
    cout<<c;
}