[BOJ / 백준] 2725 보이는 점의 개수 (S2^ / 수학) - Python

링크

https://www.acmicpc.net/problem/2725

 

 

 

 

문제 해석

(0, 0)에서 볼 수 있는 점의 개수를 출력하기

 

 

 

입력

첫 번째 줄 : 테스트 케이스

나머지 줄 : n

  n : x, y의 범위 제한

 

 

출력

n까지 범위 내 보이는 점의 개수

 

 

 

 

풀이 & 코드 해석

(4, 2)는 (2, 1)에 의해서 가려지기 때문에 볼 수 없습니다.

 

이를 다르게 생각하면 (a, b)에서 a, b를 나누어 떨어뜨리는 약수가 존재하는 경우,

즉 a, b의 최대 공약수가 1이 아닌 경우에는 해당 위치가 볼 수 없는 자리라고 볼 수 있습니다.

 

(※ 두 수의 최대공약수로 1만 가질 수 있는 경우를 서로소라고 합니다.)

 

 

 

한편 n이 한 칸씩 늘어날 때 마다 볼 수 있는 점의 개수는 짝수 개로 늘어납니다. (1을 제외)

 

n을 2라고 가정했을 때 새롭게 볼 수 있는 점은 (2, 1), (1, 2)입니다.

 

따라서 a와 b가 서로소라면 (a, b)는 볼 수 있는 점이며, (b, a) 역시 볼 수 있는 점이라는 것을 알 수 있습니다. 

 

 

 

 

코드

# from math import gcd

# 1이 나오면 서로소
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


t = int(input())

ans = [0, 3]

for i in range(2, 1001):
    now_ans = 0
    for j in range(1, i):
        if gcd(i, j) == 1:
            now_ans += 1

    ans.append(ans[-1] + now_ans * 2)

# print(ans)

for _ in range(t):
    n = int(input())

    print(ans[n])

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java