[Codility] Lesson12. Chocolatesbynumber (python)

1. 문제

 

2. 풀이

def solution(N, M):
    x = 0
    eat = [0]

    while(1):
        res = (x + M) % N
        if res == 0:
            break
        eat.append(res)
        x = x + M
    
    return len(eat)

처음에 while문으로 문제에 나온 그대로 풀다가 Time out...

그래서 풀이를 찾아보았다.

초콜릿을 먹는 개수는 N,M의 최대공약수의 배수 개수만큼 먹는다.

결국 최대공약수를 구하는 문제

 

3. 코드

def solution(N, M):
    a, b = N, M

    while(b):
        a, b = b, a % b
    gcd = a #최대공약수
    answer = N // gcd
    
    return answer

---

참조 : https://killong.blogspot.com/2019/12/codility-lesson12-chocolatesbynumbers.html