문제 링크 : https://www.acmicpc.net/problem/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;
}
'정보 > 백준 문제풀이' 카테고리의 다른 글
백준 30928번 Yokohama Phenomena C++ (1) | 2024.03.23 |
---|---|
백준 8983번 사냥꾼 C++ (0) | 2024.03.19 |
백준 1011번 Fly me to the Alpha Centauri C++ (1) | 2024.02.08 |
백준 1654번 랜선 자르기 C++ 이분탐색 (0) | 2024.01.27 |
백준 1713번 후보 추천하기 C++ (1) | 2024.01.06 |