[문제]
https://school.programmers.co.kr/learn/courses/30/lessons/12942
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[풀이]
https://stritegdc.tistory.com/180
[boj] 백준 11049 행렬 곱셈 순서 (c++) - dp
[문제] https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한,
stritegdc.tistory.com
위 문제와 같은 문제임.
[코드]
class Solution {
public int solution(int[][] matrix_sizes) {
int answer = 0;
// 모든 행렬을 곱하기 위한 최소 곱셈 연산의 수를 return
int len = matrix_sizes.length;
//dp[i][j] = i~j까지 행렬 곱의 최소 곱셈 연산 수
int[][] dp = new int[len][len];
//구간 범위 크기
for(int i=1; i<=len; i++){
//시작 지점
for(int j=0; j+i<len; j++){
dp[j][i+j] = Integer.MAX_VALUE;
//중간 지점
for(int k=j; k<j+i; k++){
dp[j][i+j] = Math.min(dp[j][i+j], dp[j][k] + dp[k+1][i+j] + matrix_sizes[j][0]*matrix_sizes[k][1]*matrix_sizes[i+j][1]);
}
}
}
answer = dp[0][len-1];
return answer;
}
}
'알고리즘 공부 및 문제 풀이 > 프로그래머스(PRO)' 카테고리의 다른 글
[pro] 프로그래머스 level4 42897 도둑질 (Java) - dp (0) | 2023.02.05 |
---|---|
[pro] 프로그래머스 level3 42627 디스크 컨트롤러 (Java) - 힙(우선순위 큐) (0) | 2023.02.03 |
[pro] 프로그래머스 level3 42579 베스트앨범 (Java) - 해쉬 (0) | 2023.02.02 |
[pro] 프로그래머스 level3 12987 숫자 게임 (Java) - 그리디, 투포인터 (0) | 2023.02.02 |
[pro] 프로그래머스 level3 12971 스티커 모으기2 (Java) - dp (0) | 2023.01.31 |