5   4   2   6   9   3   8   7    를 분배하려고 한다   


두수의 차이를 트리로 만듬 



            1  0

          1  0  0    

        0   1   1  1                        3

      1   1   2   2   3                      9   

    1   2   1   3   1   4                   12

  1   2   4   3   6   5   1               22

5   4   2   6   9   3   8   7             55


3등분 하려 하기때문에 트리의 2번째줄 1 0 0 에서 시작 



     1 / 0 / 0    

        0   1   1  1                        3

      1   1   2   2   3                      9   

    1   2   1   3   1   4                   12

  1   2   4   3   6   5   1               22

5   4   2   6   9   3   8   7             55



한줄 내려오면 다음 줄은 0111  합은 3  3등분 하려 하기 때문에 각 항은 1씩 가져야 한다 


     1 / 0 / 0    

        0   1   1  1                        3

      1   1   2   2   3                      9   

    1   2   1   3   1   4                   12

  1   2   4   3   6   5   1               22

5   4   2   6   9   3   8   7             55




다음줄은 11223  합은9 3등분 하기때문에 각 항이 3이되면 제일 좋으나 안되면  둘을 비교하여 가장 근사값으로 간다.


예   11 / 22 /3   112 / 2 / 3 


     1 / 0 / 0    

        0   1 / 1 / 1                        3

      1   1 / 2   2 / 3                      9   

    1   2   1   3   1   4                   12   /3 = 4

  1   2   4   3   6   5   1               22

5   4   2   6   9   3   8   7             55



여하튼 계속 진행하면    나누는 / 마크는 자기 기준으로 왼쪽 아래나 오른쪽 아래로 밖에 못움직임 



   1 / 0 / 0    

        0   1 / 1 / 1                        3

      1   1 / 2   2 / 3                      9   

    1   2   1 / 3   1 / 4                   12   /3 = 4

  1   2   4 / 3   6 / 5   1               22  /3 = 7.3

5   4   2   6   9   3   8   7             55  /3 = 17



설명  5번째 줄에있는 124 36  , 그사이에 있는 / 는

자기 왼쪽 아래나  


 1  2  4 / 3  6 / 5  1  

5  4  2 / 6  9  3  8  7


자기 오른쪽 으로 밖에 못내려가는데 


 1  2  4 / 3  6 / 5  1  

5  4  2  6 / 9  3  8  7


각 줄의 합을  3으로 나눈 평균에 근사한 값으로 구한다. 


그러므로 


5  4  2  6 / 9  3  8  7 가 맞다 .





다른예 



1  10000  2  3   의 경우 


2묶음으로 나눌려고 할때


1         9997

    9999        9998      1

1        10000        2        3  





1     /     9997

    9999         9998      1

1        1000        2        3  






1     /     9997

    9999    /     9998      1

1        10000        2        3       10006/2 = 5003   


9999 와 9998 사이에 있는 / 는 


1 / 10000   2   3 


1 10000 /  2  3 


두가지로 내려갈수가 있는데 


5003에 가까운걸 선택 



1 10000 /  2  3