[백준] 2725번 보이는 점의 개수

💡문제접근

• N의 값을 따졌을 때, 점이 보이려면 기울기의 분자, 분모 값이 서로소 관계여야 (0, 0)에서 보이는 점이 된다. 분자, 분모의 값이 서로소 관계가 성립하려면 분자, 분모의 최대공약수는 1이어야 한다.

💡코드(메모리 : 31256KB, 시간 : 216ms)

import sys
input = sys.stdin.readline

def GCD(x, y):
    while y > 0:
        x, y = y, x % y
    return x

dp = [0] * 1001
dp[1] = 3
for i in range(2, 1001):
    cnt = 0
    for j in range(1, i+1):
        if GCD(i, j) == 1:
            cnt += 2
    dp[i] = dp[i-1] + cnt

C = int(input())
for _ in range(C):
    N = int(input())
    print(dp[N])

💡소요시간 : 27m