15933번 - 행렬 곱셈 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 112 | 34 | 23 | 37.705% |
문제
n개의 행렬 M1, M2, ..., Mn 이 주어진다. 행렬 Mi (i = 1, 2, ..., n)은 R[i]개의 행, C[i]개의 열을 가지고 있다 (R[i] x C[i]).
정수 i(1 ≤ i ≤ n)에 대해서, 아래와 같이 정의되는 값 Vi를 계산하려고 한다.
먼저, i개의 행렬 M1, M2, ..., Mi을 모두 곱할 수 있는 순서가 있는지 알아본다. 참고로 행렬 곱셈 연산에서 RxC 행렬과 R'xC' 행렬을 곱하려면 C = R'이 성립하여야 하고 결과로 나오는 행렬은 RxC'이다. 만약 i개의 행렬을 (순서를 자유롭게 재배치 하더라도) 곱하는 것이 불가능하다면 Vi = 0 으로 정의된다. 만약 가능하다면, 가능한 모든 방법 중 최종 결과가 되는 행렬의 크기가 가장 커지는 방법을 찾아 그 때 결과로 나온 행렬의 크기 (행의 수 x 열의 수)가 Vi 값이 된다.
V1, V2, ..., Vn를 구해보자.
입력
첫째 줄에는 자연수 n이 주어진다 (1 ≤ n ≤ 1,000). 다음 n줄에는 각 줄에 정수 두 개가 주어지는데, 각 행렬의 행의 수 R[i]와 열의 수 C[i]이다. 각 행렬의 행의 수와 열의 수는 1 이상 1,000 이하이다.
출력
총 n줄을 출력해야 하고, 각 줄에는 V1 부터 Vn까지 Vi 값을 출력한다.
서브태스크 1 (5점)
- 1 ≤ n ≤ 10
- 1 ≤ R, C ≤ 1,000
서브태스크 2 (10점)
- 1 ≤ n ≤ 1,000
- 1 ≤ R, C ≤ 1,000
예제 입력 1
3 8 2 2 8 2 2
예제 출력 1
16 64 64
i = 1 일 때에는 8x2 행렬 (M1) 하나만 이용하여 원소의 수가 총 16개인 행렬을 만들 수 있다.
i = 2 일 때에는 M1 x M2 를 하여 8x8 행렬을 만들 수 있고, 원소의 수는 총 64개이다. 혹은 M2 x M1 을 하여 2x2 행렬을 만들 수 있지만, 원소의 수가 최대가 되는 방법은 상기한 방법이다.
i = 3 일 때에는 M1 x M3 x M2를 통해 8x8 행렬을 만들 수 있다.
예제 입력 2
3 4 9 9 1 9 9
예제 출력 2
36 4 4
예제 입력 3
3 4 10 10 1 10 6
예제 출력 3
40 4 0
i = 3일 때 어떤 순서로 3개의 행렬을 배치하여 곱하더라도 행렬 곱셈 연산을 완료할 수 없으므로 답이 0이다.
예제 입력 4
3 10 3 3 10 5 5
예제 출력 4
30 100 0
예제 입력 5
4 1 1 1 1 1 1 1 1
예제 출력 5
1 1 1 1
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호