백준2168 - 타일 위의 대각선

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

2168번: 타일 위의 대각선

오늘 윈터코딩 테스트에 나왔던 첫번째 문제다. 윈터코딩에서는 사용할 수 있는 정사각형의 갯수를 물었지만 문제에서는 대각선이 그어지는 정사각형의 갯수를 물었다. 규칙은 다음과 같다. 규칙 찾는데 하루종일 걸린 것 같다.

 

ex1). 가로 4, 세로 6

최대 공약수 : 2

대각선이 그려지는 정사각형 : 4 + 6 - 2 = 8

 

ex2). 가로 3, 세로 5

최대 공약수 : 1

대각선이 그려지는 정사각형 : 3 + 5 - 1 = 14

 

ex3). 가로 8, 세로 12

최대 공약수 : 4

대각선이 그려지는 정사각형 : 8 + 12 - 4 = 16

 

#include <iostream>
using namespace std;

//최대 공약수, 재귀 호출을 이용
int gcd(int x, int y) {
	if (y == 0) {
		return x;
	}
	else {
		return gcd(y, x % y);
	}
}

int main() {
	long long int m, n;
	long long int g;
	cin >> m >> n;
	g = gcd(m, n);
	cout << m + n - g; //가로 + 세로 - 최대공약수를 하면 답이 나온다.
}