모든 양의 유리수는 단위분수의 합으로 나타낼 수 있다

1. 단위분수

 

분자가 1이고 분모가 양의 정수인 분수

 

1/1, 1/2, 1/3,...이 단위분수이다.

 

1/(1.5)라든지 1/(3.4)같이 분모가 실수이면 단위분수가 아니다.

 

흥미로운 점은 모든 유리수는 어떤 단위분수들의 합으로, 여러가지 방법으로 나타낼 수 있다는 점이다.

 

$$\frac{4}{5} = \frac{1}{2} + \frac{1}{4} + \frac{1}{20} = \frac{1}{3} + \frac{1}{5} + \frac{1}{6} + \frac{1}{10}$$

 

단위분수들의 합을 이집트 분수(Egyptian fraction)라고 부른다

 

이렇게 나타내는 방법에 대해 여러가지 연구들이 있다..

 

https://en.wikipedia.org/wiki/Egyptian_fraction

Egyptian fraction - Wikipedia

 

 

실용적으로 피자 5판을 8명이서 나눠먹는다고 할때, 각 사람은 피자를 얼마나 받아야하는가?

 

$$\frac{5}{8} = \frac{1}{2} + \frac{1}{8}$$이므로, 피자 반판 + 피자 1/8판을 받아야한다는 것을 의미한다.

 

그렇다면 관심이 생기는 부분은 이러한 이집트 분수 표현법을 어떻게 찾을 수 있을까?

 

여러가지 방법이 있지만 알고리즘적으로 생각할 수 있는 좋은 방법 중 하나가 피보나치의 그리디 알고리즘이다.

 

주어진 분수 m/n에서 뺄 수 있는 가장 큰 단위 분수를 0이 될때까지 빼면 된다.

 

예를 들어 9/20은 9/20 - 1/3 = 7/60

 

7/60 - 1/9 = 1/180

 

1/180 - 1/180 = 0

 

이므로, 9/20은 1/3 + 1/9 + 1/180이다.

 

2. 연습문제 1

 

4587번: 이집트 분수

 

위의 피보나치 그리디 알고리즘에 따라 주어진 유리수를 단위분수의 합으로 나타내는 문제이다.

 

그런데, 이 그리디 알고리즘은 단위분수의 분모가 매우 커질 수 있다는 문제가 있다.

 

그래서 단위분수를 빼고 난 뒤에 나온 분수의 분모가 1000000보다 작게 제한을 두고자 한다.

 

from sys import stdin

def gcd(a,b):
    
    while b != 0:
        
        a,b = b,a%b
    
    return a

upper = 1000000

while 1:
    
    m,n = map(int,stdin.readline().split())

    if m == 0 and n == 0:
        
        break

    answer = []

    while 1:
        
        j = n/m
        
        if n % m != 0:
            
            j = int(j) + 1
        
        else:
            
            j = int(j)

        for i in range(j,upper):
        
            #m/n - 1/i = (mi - n)/ni

            mm = m*i-n
            nn = n*i

            if mm >= 0:

                g = gcd(mm,nn)

                mm = mm//g
                nn = nn//g
            
                if nn < upper:
                    
                    answer.append(i)
                    j = i
                    m = mm
                    n = nn
                    break
        
        if m == 0 and n == 1:
            
            break
    
    print(*answer)

 

 

분수 m/n이 주어질때, 1/1, 1/2, ..., 1/1000000 을 차례대로 빼봐서, 처음으로 분모 제한안에 들어오면 1/D1이라 하고 그걸 선택

 

그리고 나서는 1/D1, 1/D1+1, 1/D1+2,..., 1/1000000을 차례대로 빼서 처음으로 분모 제한안에 들어오면 1/D2

 

....

 

이런식으로 범위를 좁혀나가면서 다 해보면 된다.

 

그런데 이러면 시간이 좀 걸릴 수 있는데 그나마 첫 시작점을 빠르게 잡을 수 있다

 

m/n에서 뺄 수 있는 가장 큰 단위분수 1/d라고 한다면 m/n >= 1/d인데, 1/d가 가장 커야하므로 d가 최솟값이어야한다.

 

여기서 역수를 취하면 n/m <= d이다.

 

따라서 d는 n/m이상의 가장 작은 정수이다. 

 

그러므로 현재 분수 m/n에 대하여 n/m = x.a1a2a3... 이런식으로 나눠보고 이거 이상의 가장 작은 정수를 찾는다.

 

이는 n이 m으로 나누어 떨어지면 n//m일거고 n이 m으로 나누어 떨어지지 않으면 n//m+1일 것이다.

 

upper = 1000000

while 1:
    
    m,n = map(int,stdin.readline().split())

    if m == 0 and n == 0:
        
        break

    answer = []

    while 1:
        
        j = n/m
        
        if n % m != 0:
            
            j = int(j) + 1
        
        else:
            
            j = int(j)

 

 

이러한 i = j부터 i = upper = 1000000까지의 단위분수에 대해 시도해본다.

 

이때 m/n - 1/i = (m*i-n)/n*i일건데, 이를 gcd를 구해서 기약분수로 나타내고

 

그 기약분수의 분자 mm이 0 이상의 양수여야하고, 분모 nn은 upper보다 작아야한다.

 

이를 만족하면 바로 통과하고 그 단위분수를 선택

 

위 과정을 0이 될때까지 반복

 

    while 1:
        
        j = n/m
        
        if n % m != 0:
            
            j = int(j) + 1
        
        else:
            
            j = int(j)

        for i in range(j,upper):
        
            #m/n - 1/i = (mi - n)/ni

            mm = m*i-n
            nn = n*i

            if mm >= 0:

                g = gcd(mm,nn)

                mm = mm//g
                nn = nn//g
            
                if nn < upper:
                    
                    answer.append(i)
                    j = i
                    m = mm
                    n = nn
                    break
        
        if m == 0 and n == 1:
            
            break

 

 

3. 연습문제 2

 

2404번: 단위 분수로 분할

 

이번엔 주어진 분수의 단위분수 분할의 개수를 구하는 문제

 

여기서 2/3 = 1/2 + 1/6인데 이것의 순서를 바꾼 1/6 + 1/2는 서로 같은 것이라고 친다.

 

먼저 주어진 분수 p/q를 기약분수로 나타낸다.

 

def gcd(a,b):

    while b != 0:

        a,b = b,a%b

    return a

p,q,a,n = map(int,input().split())

g = gcd(p,q)

p = p//g
q = q//g

 

 

초기값을 y/x = 0/1이라 두고 1/1, 1/2,... 순서대로 하나하나 더해가며 DFS로 답을 찾는다.

 

먼저 핵심은 현재 1/3을 선택해서 dfs를 진행한다면, 다음에는 다시 1/1,1/2,..부터 시작하는게 아니라

 

1/3,1/4,1/5...부터 시작해야하는 것이다.

 

왜냐하면 1/2 + 1/6과 1/6 + 1/2는 서로 같은것으로 치니까 분모를 작은것부터 큰 순서대로 정렬한다는 거지

 

그리고 1/i를 선택했다면 조건에 따라 이전까지 선택한 단위분수들의 분모 v에 대하여 v*i가 a이하여야한다.

 

그렇게 선택했다면, 현재 분수 합 y/x + 1/i = (yi + x)/xi이므로, 이를 기약분수로 나타내 yy/xx라고 하자.

 

이제 다음 dfs로 들어가면 된다.

 

만약 v*i > a이면, 그것보다 큰 i를 선택하더라도 무조건 vi > a이므로 for문을 더 돌지말고 return해야한다.

 

def dfs(y,x,j,v,m):

    for i in range(j,a+1):
        
        #y/x + 1/i = (iy + x)/xi

        if v*i <= a:
            
            
            g = gcd(x + y*i,x*i)
            
            yy = (x+y*i)//g
            xx = (x*i)//g

            dfs(yy,xx,i,v*i,m+1)
        
        else:
            
            return

 

 

이때 현재 선택된 분수의 개수 m개가 n개 이하이면, 조건을 모두 만족하고 있으므로, 

 

현재 값 y/x가 목표로 하는 p/q와 동일한지 체크해야한다. 모두 기약분수니까 y = p, x = q이면 카운팅

 

그런데 현재 m = n이면 더 이상 진행할 필요가 없으므로 return해준다.

 

마찬가지로 분수를 계속 더해가고 있으므로 y/x >= p/q이면 더 할 필요가 없다.

 

이는 정수 계산으로는 yq >= xp이다.

 

count = 0

def dfs(y,x,j,v,m):
    
    global count

    if m <= n:
        
        if y == p and q == x:
            
            count += 1
    
    if m == n:
        
        return
    
    #y/x > p/q
    #qy > px

    if q*y >= p*x:
        
        return

    for i in range(j,a+1):
        
        #y/x + 1/i = (iy + x)/xi

        if v*i <= a:
            
            
            g = gcd(x + y*i,x*i)
            
            yy = (x+y*i)//g
            xx = (x*i)//g

            dfs(yy,xx,i,v*i,m+1)
        
        else:
            
            return
     
dfs(0,1,1,1,0)

print(count)