[백준 2168 : JAVA] 타일 위의 대각선 / 수학

문제

---

 

 

 

풀이

---

먼저, 분자와 분모의 최대공약수가 1인, 쉽게 말해 $\frac{3}{2}$, $\frac{4}{3}$ 와 같은 기약분수 형태에 대해 그림을 그려보자.

 

[그림 1] 직사각형에 대각선을 그은 모습

 

위의 그림을 통해 직사각형에 대각선을 그으면 $(x-1)$개의 세로줄, $(y-1)$개의 가로줄을 지난다는 것을 알 수 있다.

즉, 대각선이 그어진 타올의 수는 처음 선을 긋기 시작한 타올의 수를 더한 $(x-1)+(y-1)+1$ 이라는 것을 알 수 있다.

 

최대공약수가 2 이상인 것 부터는 중간에 최대공약수가 1인 지점을 기준으로 가로줄, 세로줄이 아닌 꼭지점을 지나게 되므로 의미가 없다.

즉, 최종 식을 도출해보면 $gcd(x, y) * ((x / gcd(x, y)-1)+(y / gcd(x, y)-1)+1)$ 이 된다.

 

위에서 도출된 식을 풀어쓰면 $x+y-gcd(x, y)$ 라는 간단해진 식을 얻을 수 있다.

 

 

 

코드

---

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int gcd = gcd(x, y);

            System.out.println(x + y - gcd);
        } catch (Exception ex) {
            ex.getMessage();
        }
    }

    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}