[BOJ 2168 // C++] 타일 위의 대각선

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2168번 문제인 타일 위의 대각선이다.
문제는 아래 링크를 확인하자.

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

2168번: 타일 위의 대각선

가로 x와 세로 y가 서로소인 경우를 생각해보자. 이 때 대각선은 각 타일의 꼭짓점 위를 지나지 않는다는 점을 확인하자.

대각선을 출발점부터 따라 끝점까지 살펴볼 때, 새로운 칸을 지나게 되는 때는 타일의 가로 경계선 또는 세로 경계선을 지날 때와 같다는 점을 관찰하자. 즉, 대각선이 새로 지나는 타일의 개수는 (가로 경계선의 수) + (세로 경계선의 수)와 같다.

위의 계산에는 대각선이 출발해 처음 만나는 첫 칸이 포함되어있지 않으므로, 위의 값에 1을 더해 답을 구할 수 있다.

 

가로 x와 세로 y가 서로소가 아닌 경우 이 대각선은 가로 x/gcd(x,y)와 세로 y/gcd(x,y)인 직사각형을 gcd(x,y)번 지나가는 것과 같다는 점을 이용해 문제를 해결하자. (단, gcd(x,y)는 x와 y의 최대공약수이다.) 최대공약수는 유클리드 알고리즘(Euclidean algorithm)을 이용해 구할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int gcd(int x, int y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int x, y; cin >> x >> y;
	int gcdxy = gcd(x, y);
	x /= gcdxy, y /= gcdxy;

	cout << (x + y - 1) * gcdxy;
}