BOJ 26073 외로운 곰곰이는 친구가 있어요

문제 링크입니다.

이동 조합하기

상하 방향과 좌우 방향으로의 이동은 서로 독립적으로 작동합니다. 그러니 갈 수 있는 거리들을 적당히 조합해서 X와 Y를 모두 만들 수 있어야 합니다.

두 이동을 조합해서 작은 단위 이동을 만들 수 있으면, 두 이동을 조합해서 쓰는 대신 조합해서 만든 단위 이동을 사용해도 충분합니다. 예를 들어, 4와 6을 조합하면 한쪽으로 6만큼 갔다가 4만큼 돌아와서 2만큼 움직이는 게 최소이므로, 두 이동의 조합을 생각하는 대신 2만큼 움직이는 단위 이동을 생각하는 것으로 충분합니다.

단위 이동 계산하기

두 이동 A, B에 대해 A = ag, B = bg (a, b는 서로소) 라고 합시다. 그러면 A와 B를 어떻게 조합해도 그 변위는 g의 정수 배가 됩니다.

a, 2a, … , ba를 b로 나눈 나머지는 모두 다릅니다. 만약 나머지가 같은 것이 있다면, 둘의 차 ka가 b로 나누어떨어진다는 뜻이 되고, k가 b보다 작으므로 ka가 b로 나누어떨어지기 위해서는 a와 b의 공약수로 1을 초과하는 수가 필요해지기 때문입니다.

b로 나눈 나머지는 0부터 b-1의 b가지 중 하나이므로, a, 2a, …, ba 중에 b로 나눈 나머지가 1인 것이 반드시 존재합니다. 이걸 ca라고 하면, ca+db = 1인 d 역시 존재합니다. 따라서 A, B를 조합해서 만들 수 있는 단위 이동의 길이는 A와 B의 최대공약수 g입니다.

따라서 주어진 모든 이동 거리의 최대공약수를 구해, X와 Y가 각각 그 값으로 나누어떨어지는 지 확인하는 것으로 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;

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

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n; cin >> n;
	while(n--){
		int x, y; cin >> x >> y;
		int k; cin >> k;
		int a[40]={};
		for(int i = 0; i < k; i++){
			cin >> a[i];
			a[0] = gcd(a[i], a[0]);
		}
		if(x%a[0] || y%a[0]) cout << "Gave up\n";
		else cout << "Ta-da\n";
	}
}