[백준 02168] 타일 위의 대각선 [Java]

문제

http://boj.ma/2168

2168번: 타일 위의 대각선

 

---

풀이

문제 요약

1x1로 이루어진 좌표평면에서 각 변의 길이가 X, Y인 직각삼각형의 빗변이 지나가는 1x1 면적의 수를 구해라.

아이디어

빗변의 기울기는 X와 Y로 결정되며, 빗변이 1x1 타일의 선이 아닌, 점을 지나는 경우는 max(x, y) / gcd(X, Y)마다 존재할 것이다.

만약 gcd가 1이라면 빗변의 시작과 끝을 제외하고는 점을 지나는 경우는 없다. 이를 표현하면 다음과 같다.

        if (gcd == 1) {
            // Output
            System.out.println(X + Y - 1);
        } else {
            System.out.println(X + Y - gcd);
        }

풀이 시간

20분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/02168.java

problem-solving/baekjoon-online-judge/easy/02168.java at main · rogi-rogi/problem-solving