Permanent Computation > 문제은행

본문 바로가기


알고리즘 다이나믹2

2043 : Permanent Computation

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 88 회    시도횟수: 179 회   



p를 {1, 2,..., n}으로 구성된 모든 순열의 조합이라고 가정하자. N x N의 행렬 A가 주어졌을 때 A[1][p[1]] * A[2][p[2]] * ... * A[n][p[n]] 의 모든 합을 구하는 프로그램을 작성하라. 가령 3 x 3의 행렬이 다음과 같이 주어졌다고 가정하자.


 

7ce7f2eba5731c8babe39036322897a0_1449819

위의 경우 모든 순열에 대한 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


입력의 첫줄에는 배열의 크기 N(1<=N<=16) 이 입력되며, 그 다음 N줄마다 N개의 행렬의 원소가 입력된다. 
각각의 원소는 빈칸으로 구분되며, 행렬의 원소의 크기는 0 보다 크고 10,000 보다 작은 정수로 이루어져 있다.


입력에 대한 합의 마지막 4자리만 출력한다. 다시 말해서 합이 99999 일 경우 9999를 출력하면 된다.

[Copy]
3 
1 2 3 
4 5 6 
7 8 9
[Copy]
450



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.