백준 : 관중석(10166) JAVA

이문제는 완전탐색 문제다.    원을 등분하여 몇번째 자리인지 check 하는 것이 중요하다.

 

3 번째 높이 관중석에 1번째 관중석의 각도는 1 / 3 이된다. 이것은  6번째 높이의 2 번째 관중석의 각도와 똑같다.

 

 2 / 6 == 1 / 3   최대 2000까지 잇으므로 boolean 배열을 선언해서 gcd를 통해 분수를 기약분수로 나타냇을 때 

 

관중석을 놔둬도 되는지 안되는지 판벼할 수 있다.

 

import java.util.Scanner;

public class 관중석 {

	static boolean View[][] = new boolean[2001][2001];

	static int GCD(int a, int b) {
		// a >= b

		while (b != 0) {
			int c = a % b;
			a = b;
			b = c;
		}
		return a;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int D1 = sc.nextInt();
		int D2 = sc.nextInt();
		long ans = 0;
		for (int i = D1; i <= D2; i++) {

			// 1 ~ i 까지 중복체크
			// 기약 분수로 나타냇을때 중복이 안되면 더한다.
			// 결국 완탐..
			for (int j = 1; j <= i; j++) {
				// 1 / 1 북쪽 좌석
				int gcd = GCD(i, j);
				if (View[i / gcd][j / gcd])
					continue;
				ans++;
				View[i / gcd][j / gcd] = true;
			}

		}
		System.out.println(ans);

	}
}