[Java] 백준 16970번 : 정수 좌표의 개수

문제

16970번: 정수 좌표의 개수

---

 

접근 방법

1. 어떤 점들이 주어졌을때 이 선분의 기울기는 y2-y1/x2-x1 입니다. 예를들어 0,0과 6,3이라는 점이 주어졌을때 이 점을 지나는 점의 갯수는 (0,0), (2,1), (4,2), (6,3) 이렇게 4개가 주어지게 됩니다.

2. 따라서 최대공약수를 사용하여 dx와 dy의 최대공약수를 구하고 1을 더하면(시작점을 포함하기 때문에) 해당 선분이 지나가는 격자점의 총 수를 구할 수 있습니다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int N,M,K;
    private static int answer = 0;

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

    }
    public static int gcd(int x, int y){
        if(x == 0 || y == 0){
            return x + y;
        }

        while(x % y != 0){
            int temp = x % y;
            x = y;
            y = temp;
        }
        return y;
    }

    //실행
    public static void process() {
        for(int x1 = 0 ; x1 <= N ; x1++){
            for(int y1 = 0 ; y1 <= M ; y1++){
                for(int x2 = 0 ; x2 <= N ; x2++){
                    for(int y2 = 0 ; y2 <= M ; y2++){
                        if(gcd(Math.abs(x2-x1), Math.abs(y2-y1)) + 1 == K){
                            answer++;
                        }
                    }
                }
            }
        }
        System.out.println(answer/2);
    }


    public static void main(String[] args) throws Exception {
        input();
        process();
    }
}