제가 틀린 말을 하고 있을지도 모르니 그냥 참고만 하세요 ^^

예시를 들어 설명하겠습니다.
n=5일 때 (변수 ={1,2,3,4,5}) n-1=4 개의 변수를 택하는 경우를 모두 나열합니다. (첨부그림 참조)
여기서 최소의 곱셈을 하기 위해서는 가장 많이 등장하는 pair에 우선순위를 두어야 합니다.
즉 그림과 같이 (1,2)와 (4,5)가 1순위겠죠.
그 다음은 ((1,2),3)과 (3,(4,5))가 됩니다.
그러면 이제 마지막으로 해야할 곱셈의 수는 row당 1개씩 남게 됩니다.

따라서 n=5일 때
2*(2)+5=9
(여기서 (2)는 (1,2)와 ((1,2),3)의 경우를 뜻하는거고 *2를 한까닭은 symmetric하기 때문이고, +5는 각각의 row당 해줘야하는 마지막 곱셈의 개수입니다.)

n=6일 때의 그림도 참조하면,
n=6일 때에는
2*(3)+6=12


따라서 n에대해 일반적으로 나타내면,
2*(n-3)+n=3n-6 이 됩니다. (단 n>3, n=3일 때는 위의 방법이 적용이 안됨을 쉽게 알 수 있죠.)

감사합니다.
* administrator님에 의해서 게시물 이동되었습니다 (2007-03-06 13:42)