[백준 2168번] 타일 위의 대각선

문제 링크: 2168번 타일 위의 대각선

https://www.acmicpc.net/problem/2168

 

가로 길이를 x, 세로 길이를 y라 하고 GCD(x, y) = G라 하면,

x = GX, y = GY와 같이 표현할 수 있다.

이 때 대각선의 기울기는 y/x = GY/GX = Y/X이고,

가로로 X칸, 세로로 Y칸 이동할 때마다 타일의 경계점과 만난다.

 

대각선 위에 X*Y의 사각형은 G개 있고,

대각선을 우하향으로 그린다고 할 때 그려진 타일은 반드시 왼쪽 상단에서 우측 하단으로 한 칸씩 이동하므로

각 사각형마다 x+y-1개의 타일에 대각선이 지나간다.

 

따라서 대각선이 그려져 있는 타일의 개수는 G*(X+Y-1)개이다.

 

여기서 최대공약수를 빨리 구하는 방법을 헤맸는데 유클리드 호제법을 떠올려야 한다.

임의의 정수 a, b(a>b)에 대하여 GCD(a, b)=G(a%b, a)이다.

a 또는 b가 0일 때까지 재귀적으로 함수를 적용해줌으로써 최대공약수를 빠르게 구할 수 있다.

증명은 여기에서 확인할 수 있다.

 

#include <iostream>

using namespace std;

int gcd(int a, int b) {
    if (a==b) return a;
    if (!a) return b;
    if (!b) return a;
    
    if (a>b) return gcd(a%b, b);
    else return gcd(a, b%a);
}

int main() {
    int m, n;
    cin >> m >> n;
    int g = gcd(m, n);
    printf("%d", gcd(m,n)*(m/g+n/g-1));
    return 0;
}