[2168번] 타일 위의 대각선

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 수학

이 문제는 타일 위에 대각선을 그엇을 때, 몇개의 타일을 지나냐인데 예제 입력에서 가로 8 세로 12라고 생각했을 때

기울기가 3/2임을 알 수 있다. 이때 2의 배수마다 타일의 꼭지점을 지나게 된다.

결국 세로 12가 될 때까지 2의 배수를 이용하면 0, 3, 6, 12가 된다.

이때 규칙을 찾아보면 알 수 있는 것은 8과 12의 최대 공약수가 4가 된다는 것임을 알 수 있고

결국 x + y - gcd(x,y)이 정답이 된다. 즉, 예제의 답은 8 + 12 - 4인 16이 답이 된다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <cmath>
 
using namespace std;
 
int gcd(int a, int b) { return !b ? a : gcd(b, a%b); }
 
int main()
{
    int x, y;
    scanf("%d %d", &x, &y);
 
    int m = gcd(x, y);
 
    int ans = x + y - m;
 
    cout << ans;
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>