ACMICPC 2942 퍼거슨과 사과

문제집 : 간단한 수학 문제 (

https://www.acmicpc.net/workbook/view/4)

문제

맨체스터 유나이티드의 감독 퍼거슨은 빨간 사과를 R개, 초록 사과를 G개 가지고 있다. 

훈련장에 있는 선수들 중 몇 명에게 나누어 주려고 한다. 단, 선수들이 서로 같은 개수의 사과를 받지 못하면 

경기력 저하가 나타날 수 있으므로 모든 선수에게 같은 개수를 주려고 한다. 퍼거슨 감독은 사과를 싫어한다. 

따라서 사과가 남으면 안된다.

예를 들어, 퍼거슨이 빨간 사과를 4개, 초록 사과를 8개 가지고 있다면, 

다음과 같이 세가지 방법으로 나누어 줄 수 있다.

1. 선수 1명에게 빨간 사과 4개와 초록 사과 8개를 줄 수 있다.
2. 선수 2명에게 빨간 사과 2개와 초록 사과 4개를 각각 줄 수 있다.
3. 선수 4명에게 빨간 사과 1개와 초록 사과 2개를 각각 줄 수 있다.

퍼거슨이 사과를 나누어 주는 방법을 구하는 프로그램을 작성하시오. 훈련장에 선수는 무한히 많다.

입력

첫째 줄에 R과 G가 주어진다. (1 ≤ R, G ≤ 1,000,000,000)

출력

퍼거슨이 사과를 나누어 주는 방법을 출력한다. 

방법을 출력할 때는 사과를 받게되는 선수의 수 N과 

나누어 주는 빨간 사과의 수 X와 초록 사과의 수 Y를 출력한다.

각 방법은 한 번만 출력해야 한다. 나누어 주는 방법은 아무 순서로 출력해도 된다.

퍼거슨과 사과, 선수들이 어쩌구 하니 복잡해 보이는데, 생각해보면

요구하는 문제는 이거다.

'숫자 2개 줄테니 공약수 찾아와'

유클리드 호제법을 이용해 최대공약수 (GCD)를 구하고 이를 통해서

공약수들을 구해내면 끝!

인데 시간초과 나버렸다. 최대 공약수까지는 좋은데,

약수 구하는 쪽에서 시간초과 난 듯 싶다...

def findGCD(a, b): while (b != 0): temp = a%b; a = b; b = temp; return int(abs(a)); def findDivisor(num): arr = []; for i in range(1, num+1): if (num%i == 0): arr.append(i); return arr; R, G = [int(x) for x in input().split()]; GCD = findGCD(R, G); CD = []; CD = findDivisor(GCD); for divisor in CD: print ("%d %d %d" %(divisor, R/divisor, G/divisor));

brute-forcing으로 풀어도 충분할 줄 알았는데 입력 한계값이 십억이더라..

R, G 값이 둘다 십억이면 뭐...시간초과 날 만 하네.

공약수 구하는 법을 좀 바꿔서 루트2 해주고 약수 a가 나오면

N/a 값도 약수이니 반만큼만 구하게 해주니

brute-forcing이 N번만큼의 계산을 해야했다면

간단히 계산해도 N**(0.5)/2 만큼의 계산만 해주면 된다.

성공!

def findGCD(a, b): while (b != 0): temp = a%b; a = b; b = temp; return int(a); R, G = [int(x) for x in input().split()]; GCD = findGCD(R, G); for i in range(1, int(GCD**0.5)+1): if (GCD%i == 0): print ("%d %d %d" % (i, R/i, G/i)); if (i != GCD/i): k = GCD/i print ("%d %d %d" % (k, R/k, G/k));