[python] 백준 2942 - 퍼거슨과 사과

빨간 사과 R개, 초록 사과 G개를

선수에게 같은 개수로 나눠주려고 하고, 사과가 남으면 안된다.

사과를 나누어주는 방법을 구하는 프로그램 작성

 

🔶시간초과

import sys
R,G=map(int,sys.stdin.readline().split())

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

li=[]

for i in range(1,gcd(R,G)+1):  #R,G의 최대공약수(gcd(R,G))의 약수 구하기
    if gcd(R,G)%i==0:  
        li.append(i)
    else:
        pass

for i in li:  #gcd의 약수만큼
    print(i,R//i,G//i)

 

루트처리해서 메모리 줄이기

import math
import sys

R, G = map(int, sys.stdin.readline().split())


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


li = []

temp = gcd(R, G)
sqrt_temp = math.sqrt(temp)  #루트처리

for i in range(1, int(sqrt_temp)+1):
    if temp % i == 0:
        li.append(i)
        if temp // i == i:
            continue
        li.append(temp // i)

for i in li:
    print(i, R // i, G // i)