[BOJ] 2725 보이는 점의 개수 - JAVA

1. 문제

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)

---

2. 풀이

1.  count배열을 이용해서 N일때의 선 개수를 저장한다. count[1]에 미리 3을 저장했다. (수직, 수평, 대각선)

2.  count[i]는 count[i-1] 값에서 그림만큼의 점만 체크해서 더하면 된다. 점선이 이어진 파란 점끼리 같은 결과이기 때문에 둘 중 한 번만 구해서 *2한다. 이때, 빨간 점은 count[1]과 동일한 값이라 볼 필요가 없다. 따라서 내부 반복문으로 j=1부터 j=i-1까지 탐색한다.

3.  (0,0) -> (x,y)까지 가려진 점이 없는 선분이려면 같은 기울기인 선분이 없어야한다는 말과 동일하다. i,j의 최대공약수를 체크해서 그 값이 1이라면 기약분수가 된다. gcd가 1인 값만 체크해서 tmp에 +1한다.

3-1.  tmp를 사용하는 이유는 배열을 여러 번 접근하는 것보다 tmp를 사용해서 더한 뒤 한 번에 count배열에 더하는 게 좋겠다고 판단했기 때문이다.

3-2.  gcd를 알아내는 것은 유클리드 호제법을 사용했다. b!=0일 때, gcd(a,b)==gcd(b,a%b)이다. b==0이라면 gcd(a,b)==a이다.

4.  테스트케이스를 입력받으면서 count[값]을 sb에 더하고, 한 번에 출력한다.

import java.io.*;

public class BOJ_2725_보이는점의개수 {
   public static void main(String[] args) throws IOException {
      int[] count = new int[1001];
      count[1] = 3;
      int tmp;
      for(int i=2;i<1001;i++){
         tmp = 0;
         for(int j=1;j<i;j++){
            if(gcd(i,j)==1) tmp++;
         }
         count[i] = count[i-1] + tmp*2;
      }

      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int C = Integer.parseInt(in.readLine());
      StringBuilder sb = new StringBuilder();
      for(int i=0;i<C;i++){
         sb.append(count[Integer.parseInt(in.readLine())]).append('\n');
      }
      System.out.print(sb);
   }
   public static int gcd(int a, int b){
      if(b==0) return a;
      return gcd(b,a%b);
   }
}

---

3. 결과