티스토리 뷰
문제는 위와 같으며 이전에 풀었던 파일 합치기 문제와 유사하게 ABC 행렬의 곱은 (AB)C 또는 A(BC) 중 최소값을 저장하는 방식으로 문제를 해결할 수 있습니다.
예제를 살펴보면 먼저 행렬(matrix)을 [[5, 3], [3, 2], [2, 6]] 으로 저장하고 순차적인 행렬의 곱을 나타내는 dp 이차원 배열에 dp[i][i + 1] = matrix[i][0] * matrix[i][1] * matrix[i+1][1] 값을 저장합니다.
그런 다음 먼저 A(BC) 인 경우를 보면 A + BC + A(BC) 값을 구해야 하는데 A(BC) 의 값은 구하고자 행렬의 범위(A~C) 중 가장 앞 행렬(A)의 r 값과 중간 행렬(B)의 r 값 그리고 마지막 행렬(C)의 c 값을 곱해서 구할 수 있다는 것을 알 수 있습니다.
그런 다음 (AB)C 인 경우를 보면 AB + C + (AB)C 값을 구해야 하는데 (AB)C 의 값은 구하고자 행렬의 범위(A~C) 중 가장 앞 행렬(A)의 r 값과 중간 행렬(B)의 c 값(= C 행렬의 r 값) 그리고 마지막 행렬(C)의 c 값을 곱해서 구할 수 있다는 것을 알 수 있습니다.
이때는 기존 ABC 에 저장된 값과 계산된 값을 비교하여 더 작은 값을 저장하게 됩니다.
파이썬 코드는 다음과 같습니다. Pypy3 로 제출해야 시간 초과 없이 문제를 해결할 수 있습니다.
from sys import stdin
n = int(stdin.readline())
matrix = [] # 주어진 행렬 [[r, c]] 형태로 저장
for _ in range(n):
matrix.append(list(map(int, stdin.readline().split())))
dp = [[0] * n for _ in range(n)] # 순차적인 행렬 곱을 표현할 이차원 배열 생성
for i in range(n - 1):
dp[i][i + 1] = matrix[i][0] * matrix[i][1] * matrix[i + 1][1]
# 3개 이상의 행렬 곱을 구할 모든 경우마다 가장 마지막에 더해질 값 반환
def find_add_num(start, end, mid):
return matrix[start][0] * matrix[mid][0] * matrix[end][1]
for j in range(2, n):
i = 0
while i + j < n:
for k in range(i, i + j):
if dp[i][i + j] == 0:
dp[i][i + j] = dp[i][k] + dp[k + 1][i + j] + find_add_num(i, i + j, k + 1)
else:
dp[i][i + j] = min(dp[i][i + j], dp[i][k] + dp[k + 1][i + j] + find_add_num(i, i + j, k + 1))
i += 1
print(dp[0][n - 1])
자바 코드는 다음과 같습니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] matrix = new int[n][2];
for (int i = 0; i < n; i++) {
matrix[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
int[][] dp = new int[n][n];
for (int i = 0; i < n - 1; i++) {
dp[i][i + 1] = matrix[i][0] * matrix[i][1] * matrix[i + 1][1];
}
for (int j = 2; j < n; j++) {
for (int i = 0; i + j < n; i++) {
for (int k = i; k < i + j; k++) {
if (dp[i][i + j] == 0) {
dp[i][i + j] = dp[i][k] + dp[k + 1][i + j] + (matrix[i][0] * matrix[k + 1][0] * matrix[i + j][1]);
} else {
dp[i][i + j] = Math.min(dp[i][i + j], dp[i][k] + dp[k + 1][i + j] + (matrix[i][0] * matrix[k + 1][0] * matrix[i + j][1]));
}
}
}
}
System.out.println(dp[0][n - 1]);
}
}
'알고리즘' 카테고리의 다른 글
[알고리즘 / 프로그래머스] 카카오프렌즈 컬러링북 (0) | 2020.12.17 |
---|---|
[알고리즘 / 백준] 1520 - 내리막 길 (0) | 2020.12.16 |
[알고리즘 / 백준] 11066 - 파일 합치기 (0) | 2020.12.11 |
[알고리즘 / 프로그래머스] 멀쩡한 사각형 (0) | 2020.12.10 |
[알고리즘 / 백준] 10282 - 해킹 (1) | 2020.12.10 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- search
- Algorithm
- sort
- string
- 순열
- Baekjoon
- java
- 에라토스테네스의 체
- programmers
- permutation
- CodeCommit
- AWS
- BFS
- map
- 수학
- SWIFT
- array
- 프로그래머스
- spring
- EC2
- 조합
- DFS
- CodeDeploy
- CodePipeline
- 소수
- ECR
- Dynamic Programming
- Combination
- ionic
- cloudfront
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
글 보관함