백준_파일 합치기_11066[Java]
2019. 4. 24. 21:51ㆍ알고리즘문제/백준
문제
https://www.acmicpc.net/problem/11066
풀이
DP로 해결한다.
생각하기 쉽지 않아 다른 분들 코드를 참고했다.
점화식은 다음과 같다.
DP[j][i] = DP[j][s] + DP[s+1][i] + SUM[j~i]
* DP[j][i] : j에서 i까지의 파일을 합치는데 드는 최소 비용
* SUM[j~i]는 j ~ i 까지의 총합으로 SUM[i] - SUM[j-1] 이다.
/*
* 각 장은 다른 파일에 저장
* 이 다른 파일을 최종 합쳐서 완성본인 파일 하나 만듦
* 과정 : 두개의 파일을 합친다 -> 임시파일
* 이 임시파일이나 원래의 파일 두개 합쳐서 여러 장들이 연속되도록 합쳐나간다.
* 합치는 비용 : 두 파일 크기의 합
* 필요한 비용의 최소 합을 구하자
*/
코드
import java.util.Scanner; public class Main { static int T, K; static int[] fic; static int[] sum; static int[][] dp; public static void main(String[] args) { Scanner sc = new Scanner(System.in); T = sc.nextInt(); for(int test = 0; test < T; test++) { K = sc.nextInt(); fic = new int[K+1]; sum = new int[K+1]; dp = new int[502][502]; for(int i = 1; i <= K; i++) { fic[i] = sc.nextInt(); sum[i] = sum[i-1]+ fic[i]; } for (int i = 2; i <= K; i++) { for (int j = i - 1; j > 0; j--) { dp[j][i] = 999999999; for (int s = j; s <= i; s++) dp[j][i] = Math.min(dp[j][i], dp[j][s] + dp[s + 1][i]); dp[j][i] += sum[i] - sum[j - 1]; } } System.out.println(dp[1][K]); } sc.close(); } }
참고
https://stack07142.tistory.com/69
'알고리즘문제 > 백준' 카테고리의 다른 글
백준_로봇 조종하기_2169[Java] (0) | 2019.04.24 |
---|---|
백준_포도주마시기_2156[Java] (0) | 2019.04.24 |
백준_말이 되고픈 원숭이_1600[Java] (0) | 2019.04.22 |
백준_통나무 옮기기_1938[Java] (0) | 2019.04.19 |
백준_안전영역_2468[Java] (0) | 2019.04.19 |