코딜리티 lesson12 유클리디안 알고리즘(GCD: 최대공약수), ChocolatesByNumbers(?), CommonPrimeDivisors(?)

유클리디안 알고리즘

A = Q*B + R

gcd(A, B) = gcd(B, R)

 

ChocolatesByNumbers

[참고풀이]

-> 규칙?답?을 알고 보면 인풋과 아웃풋 사이의 관계가 저렇구나 알수 있지만,, 답을 알기전엔 그 상관관계(수식)를 찾기가 어려웠다

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

from math import gcd

def solution(N, M):
    return N // gcd(N, M)

 

CommonPrimeDivisors

[참고풀이]

->문제속에서 상관관계를 알아내는 것이 문제다..

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
from math import gcd

def solution(A, B):
    cnt = 0

    for i in range(len(A)):
        if isSameDivisors(A[i], B[i]):
            cnt += 1
    return cnt


def isSameDivisors(a, b):
    gcdAB = gcd(a, b) 
    gcdA = 0
    gcdB = 0

    while gcdA != 1:
        gcdA = gcd(a, gcdAB) 
        a = int(a / gcdA)

    while gcdB != 1:
        gcdB = gcd(b, gcdAB) 
        b = int(b / gcdB)
    
    if a == 1 and b == 1:
        return True
    else:
        return False