[C/C++] 백준 #2168 타일 위의 대각선(정수론)

이번 문제는 정수론(number theory)을 알면 쉽게 해결할 수 있습니다.  정수론에서 가장 기본이 되는 것 중에 하나가 최대 공약수(GCD; Greatest Common Divisor)입니다.  최대 공약수를 구해서 문제를 해결할 수 있습니다.

 

문제의 링크는 다음과 갈습니다.

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

2168번: 타일 위의 대각선

 

대각선이 그려진 타일의 개수를 구하는데, 어떻게 하면 될까요?  일단 아래의 그림을 가지고 이야기를 해보죠.

 

Paint Tiling with diagonal line

가로가 16, 세로가 5개인 타일들입니다.  대각선은 위와 같을 때, 타일과 타일의 모서리를 정확하게 지나가는 경우가 없습니다.  정확하게 지나가는 경우에는 최대공약수가 1이 아닌 경우에만 발생합니다.  바로 이러한 점에 착안을 두었습니다.  gcd가 1이라면, 위와 같이 가로의 타일 개수 + 세로의 타일 개수 - 1 이 됩니다.  gcd가 1이 아니라면요?  gcd가 1이 아니라면, 가로를 gcd만큼 나눌 수 있고, 세로를 gcd만큼 나눌 수 있습니다.  그러면 대각선이 지나가는 부분은 gcd 개수만큼 나오겠죠.  gcd 개수 안에서는 위와 같이 gcd가 1인 경우와 동일하게 계산할 수 있습니다.  그래서 다음과 같은 식을 세울 수 있습니다.

 

\[ T = ((r/g) + (c/g) -1) \cdot g = r + c - g\]

 

자 이렇게 하면 gcd를 구할 때 이외에는 바로 대각선이 지나는 타일의 개수를 구할 수 있습니다.

 

제가 작성한 소스입니다.

//------------------------------------------
//    baekjoon #2168
//        - by Aubrey Choi
//        - created at 2019-08-27
//------------------------------------------
#include <stdio.h>

int gcd(int a, int b) { while(b) { int t=b; b=a%b; a=t; } return a; }
int main()
{
    int x, y, g;
    scanf("%d%d", &x, &y);
    g=gcd(x,y);
    printf("%d\n", x+y-g);
}