2725 - 보이는 점의 개수
📌 문제
(0,0)에서 보이는 (x,y)의 개수를 구하려고 한다.(x,y >= 0, 정수)
(0,0)에서 (x,y)가 보이려면 (0,0)과 (x,y)를 연결하는 직선이 다른 점을 통과하지 않아야 한다. 예를 들어 (4,2)는 (0,0)에서 보이지 않는다. 그 이유는 (0,0)과 (4,2)를 연결하는 직선이 (2,1)을 통과하기 때문이다. 아래 그림은 0 <= x,y<=5인 경우에 (0,0)에서 보이는 점의 개수이다. 단, (0,0)은 계산하지 않는다.
N이 주어졌을 때, 원점에서 보이는 (x,y) 좌표의 개수를 출력하시오. (0 <= x,y <= N)
📋 코드
def gcd(i, j):
if j == 0:
return i
return gcd(j, i % j)
dp = [0 for _ in range(1001)]
dp[1] = 3
for i in range(2, 1001):
cnt = 0
for j in range(1, i+1):
if i == j:
continue
if gcd(i, j) == 1:
cnt += 2
dp[i] = dp[i-1] + cnt
T = int(input())
for _ in range(T):
N = int(input())
print(dp[N])💡 한마디
(0,0)에서 보이지 않으려면 직선의 기울기가 달라야 한다. 4/2나 6/3은 약분하면 둘 다 기울기가 2로 똑같다. 따라서 분자와 분모의 최대공약수가 1인 값들을 찾아내면 된다.
