p를 {1, 2,..., n}으로 구성된 모든 순열의 조합이라고 가정하자. N x N의 행렬 A가 주어졌을 때

A[1][p[1]] * A[2][p[2]] * ... * A[n][p[n]] 의 모든 합을 구하는 프로그램을 작성하라.

가령 3 x 3의 행렬이 다음과 같이 주어졌다고 가정하자.

위의 경우 모든 순열에 대한 A[1][p[1]] * A[2][p[2]] * A[3][p[3]] 의 곱들의 합은 다음과 같다.

A[1][1] * A[2][2] * A[3][3] +

A[1][1] * A[2][3] * A[3][2] +

A[1][2] * A[2][1] * A[3][3] +

A[1][2] * A[2][3] * A[3][1] +

A[1][3] * A[2][1] * A[3][2] +

A[1][3] * A[2][2] * A[3][1] = 1*5*9 + 1*6*8 + 2*4*9 + 2*6*7 + 3*4*8 + 3*5*7 = 450

Permanent Computation timer 1초 memory 64MB

Permanent Computation 1초 64MB