[백준 2168번] 타일 위의 대각선 - C++ 풀이

https://www.acmicpc.net/problem/2168
(백준 문제 링크)

1. 문제 설명

문제

한 변의 길이가 1cm인 정사각형 모양의 타일이 있다. 이 타일들을 가로가 xcm, 세로가 ycm인 직사각형 모양의 벽에 빈틈없이 붙였다. x와 y는 정수이다.

이 직사각형에 하나의 대각선을 그렸다. 직사각형에 붙어 있는 x*y개의 타일 중에는 대각선이 그려진 타일도 있고, 그렇지 않은 타일도 있다. x*y개의 타일 중에서 대각선이 그려져 있는 타일의 개수를 구하는 프로그램을 작성하시오.

2. 풀이

가로가 3, 세로가 2인 벽에 타일을 붙이면 아래 그림과 같습니다.

처음 시작된 격자에서 선이 진행되다가 격자와 격자 사이 경계선에 다다르면 새로운 영역(타일)으로 나가는 것이 되며, 해당 영역(타일)에도 선이 그어지게 됩니다. 영역 변경이 3번 일어났고, 최초 영역까지 포함하여야하기에 $3+1$ 즉 4개의 영역에 직선이 그어지게 됩니다.

영역 변경 횟수인 3회를 더 살펴보겠습니다.
가로로 보았을 때 첫번째 타일에서 두번째 타일로 이동할 때, 그리고 두 번째와 세번째 타일로 이동할 때로 가로 이동으로 인해 2번 선이 그어졌습니다.(=타일을 이동하였습니다)
세로로 보았을 때는 첫번째 타일에서 두번째 타일로 이동할 때, 1번만 이동하여 선이 1개 발생하였습니다.

즉, 좌측 하단에서 우측 하단으로 이동하기 위해서는 가로로 X-1 이동하고, 세로로 Y-1만큼 이동하여야됩니다.
그러므로 직선이 그어지는 타일의 개수는 최초 타일 1개에 타일 변경 횟수인 $(X-1) + (Y-1)$ 입니다.

하지만 이것이 끝이 아닙니다. 가로가 6, 세로가 4인 경우를 그리면 다음과 같습니다.

이전에 그렸던 가로가 3, 세로가 2인 직사각형을 두개 이어붙인 형태이며, 이어 붙인 자리 또한 영역(타일)이 변경되는 지점입니다. 위 그림의 경우에는 이전에 계산해두었던 영역 변경 횟수 4회가 2번 일어나게 됩니다.

가로 3, 세로 2 도형이 2번 붙여짐으로 가로 6, 세로 4가 되었으며, 2는 6과 4의 최대공약수(GCD)입니다.

다시 말하자면 가로와 세로 길이가 주어진 도형 내부에 특정한 형태가 몇번 반복되는지는 가로 길이 X와 세로 길이 Y의 최대공약수를 통해 계산할 수 있습니다. 또한 반복되는 특정한 형태는 가로 길이와 세로 길이에 최대공약수를 나누어봄으로써 찾아낼 수있습니다.
$(X \div GCD - 1,{ }Y \div GCD - 1)$

모든 내용을 정리하면, 이번 문제는 $GCD * ((X/GCD - 1) + (Y/GCD - 1) + 1)$을 계산하면 됩니다.

최대공약수는 유클리드 호제법을 통해 쉽게 계산 가능합니다.

3. 정답 코드

#include<iostream>
using namespace std;

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int x, y;
    cin >> x >> y;
    int GCD = gcd(x, y);
    cout << GCD * ((x/GCD - 1) + (y/GCD - 1) + 1);
}