[BOJ_2168] 타일 위의 대각선

설명

---

순서를 지켜나가면서 생각하면 쉬운 문제다.

 

1. 우리는 먼저 기약 분수의 형태로 나누어 볼 것이다. 이때, 기약 분수처럼 나누려면 x, y 값이 예를 들어서 4, 8이 들어오면 1, 2 로 기약 분수처럼 끝까지 나눌 수 있고 이 형태 자체는 최대 공약수를 나누었을때 나오는 값이다.

 

2. 이때, x , y 값의 사각형의 크기 및 대각선의 형태 반복은 1,2의 사각형이 총 4 * 4개의 형태로 이루어진다.

 

즉, 아래 그림처럼 나올 것인데 이는 또한, 1,1 정사각형의 대각선의 길이를 구하기 위해서 진행된 것이므로 여기서 중간 라인이 지나가는 것을 이렇게 볼 수 있을 것이다. 중간에 1,1 정사각형은 이해를 위해서 넣었다.

결국 이렇게 지나가는 선이 거치는 사각형의 갯수를 카운팅하기 위한 것인데 잘 보면 시작과 끝점으로 만나는 꼭지점이 최대 공약수로 나눈 1,2의  형태에서 딱 맞아 떨어지는 것을 볼 수 있다!

 

이를 참고해서 해당 1,2 작은 사각형에서 타일 선이 지나가는 사각형의 갯수를 카운팅하면 되는데 위 예제는 처음 시작하는 세로선 그후 가로선 그후 세로선의 형태가 나타나는데 이는 1,3 / 3,1 사각형으로 보고 꼭지점을 마지막 포인트로 지나게 하면 식이 보일 수 있을 것이다. 3,1의 경우 시작 가로선 -> 세로선 -> 세로선 -> 마지막 세로선 1,3의 경우 시작 세로선 -> 가로선 -> 가로선 -> 마지막 가로선

3,1

1,3

보면 공식을 쓸 수 있겠구나 싶은데 지금 1,3은 최대공약수로 나누어진 각각의 값으로 (x/GCD(x,y) + y/GCD(x,y) - 1) 이 해당 형태로 나오는 것을 볼 수 있으며 이 꼭지점이 지나가는 포인트의 사각형만 그리면 되므로 위 구한 식에다가 최대 공약수를 곱한다.

 

그러면 코드와 같은 식이 나온다.  (x/GCD(x,y) + y/GCD(x,y) - 1)  * GCD(x,y)

 

위 과정이 해당 코드의 풀이이다.

 

코드

---

package Math;

import java.util.Scanner;

public class BOJ_2168 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();

        int n = GCD(x,y);

        System.out.println(((x / n) + (y / n) - 1) * n);
    }

    private static int GCD(int x, int y) {
        if(y == 0){
            return x;
        }
        return GCD(y, x % y);
    }
}

2168번: 타일 위의 대각선