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

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

2725번: 보이는 점의 개수

 

알고리즘 분류

• 수학
• 정수론
• 누적 합
• 유클리드 호제법

 

풀이

유클리드 호제법 알고리즘과 다이나믹 프로그래밍을 이용해 풀었다.

0,0 에서 보이는 점의 갯수를 구하는 문제다.

 

예를 들어보자 

x, y 좌표가 (2, 4)인 좌표는 (1, 2)에 가려서 안보인다. 왜냐하면 기울기가 같기 때문이다. 

이 좌표가 가려서 안보이는지, 아니면 (0, 0)에서 보이는지 유클리드 호제법을 사용해 알 수 있는데,

x, y 좌표의 최대 공약수가 1이면 보이고 1이 아니면 안보인다.

아래의 그림을 통해 설명하자면 . 

 

(2, 4)의 좌표의 최대 공약수는 2이다. 따라서 안보인다고 할 수 있다. 

 

최대 공약수를 구한는 gcd 메서드이다.

public static boolean gcd(int x, int y) {
	if(y==0) return x==1;
	return gcd(y, x%y);
} // gcd

두 수가 서로소 ( 서로의 약수가 1밖에 없는 관계 ) 인지 판단하는 gcd 메서드이다.

두 수가 주어졌을 때 x와 y의 최대 공약수는 y와 x 를 y로 나눈 나머지의 최대공약수와 같다는 원리를 이용한다.

이 과정을 y가 0일 때 까지 반복해 y가 0 일때 a가 최대 공약수이다.

따라서 최대공약수가 1이면 x==1가 맞으므로 true를 반환한다. 

 

 

전에 구했던 갯수에서 새롭게 보이는 갯수만 더하면 되므로 dp를 사용해 값을 구했다.

cnt라는 값은 i ( x값 ), j (y값) 의 최대 공약수가 1이면 하나씩 증가하고 아니면 0을 더해 증가하지 않도록 했다

마지막에 2를 곱한 것은 대각선을 기준으로 한 구역만 구하므로 2를 곱했다.

dp[1] = 3;
int cnt;
   for (int i = 2; i < dp.length; i++) {
   cnt = 0;
   for(int j = 1 ; j < i ; j++) {
	  cnt += (gcd(i, j) == true) ? 1: 0;
   }
   dp[i] = dp[i-1] + 2 * cnt;
}

 

 

아래는 전체 정답 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		int temp[] = new int[n];
		for (int i = 0; i < temp.length; i++) {
			int a = Integer.parseInt(br.readLine());
			temp[i] = a;
		} // for
		
		int [] dp = new int[1000 + 1]; // 각 케이스는 1000이하
		
		dp[1] = 3;
		int cnt;
		for (int i = 2; i < dp.length; i++) {
			cnt = 0; // 보이는 갯수 구하는 변수
			for(int j = 1 ; j < i ; j++) {
				cnt += (gcd(i, j) == true) ? 1: 0; // true면 1을 더하고 false면 0을 더한다.
			}
			dp[i] = dp[i-1] + 2 * cnt;
		}
		
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < temp.length; i++) {
			sb.append(dp[ temp[i] ]).append("\n");
		} // for
		
		System.out.println(sb.substring( 0, sb.length()-1 ).toString());
		
	}
	
	public static boolean gcd(int x, int y) {
		if(y==0) return x==1;
		return gcd(y, x%y);
	} // gcd
}