[중상] 집합

문제 : http://koitp.org/problem/SET/read/

Github : https://github.com/ddulhddul/algorithm/blob/master/src/SW01_jibhab.java

소스코드

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

//class Solution {
public class SW01_jibhab {
	
	public static void main(String[] args) 
			throws FileNotFoundException 
	{

		File file =new File("D:\\dev\\worksspace\\Solution\\src\\sw01_jibhab");
		Scanner sc = new Scanner(file);
//		Scanner sc = new Scanner(System.in);
		
//		long start = System.currentTimeMillis();
		int totalCase = sc.nextInt();
		
		while (sc.hasNext()) {
			
			int N = sc.nextInt();
			int M = sc.nextInt();
			
			int[] nArr = new int[N+1];
			int[] mArr = new int[M+1];
			for (int i = 1; i <= N; i++) {
				nArr[i] = sc.nextInt();
			}
			for (int i = 1; i <= M; i++) {
				mArr[i] = sc.nextInt();
			}
			
			Arrays.sort(nArr);
			Arrays.sort(mArr);
			
			int[][] dp = new int[N+1][M+1];
			
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= M; j++) {
					if(i == j){
						if(i == 1){
							dp[i][j] = Math.abs(nArr[i] - mArr[j]);
						}else{
							dp[i][j] = dp[i-1][j-1] + Math.abs(nArr[i] - mArr[j]);
						}
					}else if(i > j){
						if(j == 1){
							dp[i][j] = Math.min(dp[i-1][j], Math.abs(nArr[i] - mArr[j]));
						}else{
							dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1] + Math.abs(nArr[i] - mArr[j]));
						}
					}else{
						if(i == 1){
							dp[i][j] = Math.min(dp[i][j-1], Math.abs(nArr[i] - mArr[j]));
						}else{
							dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j-1] + Math.abs(nArr[i] - mArr[j]));
						}
					}
				}
			}
			
			System.out.println(dp[N][M]);
					
		}
		
//		long end = System.currentTimeMillis();
//		System.out.println("time "+ (end-start)/1000.0);
	}
	
}




/*
1
2 1
10 20
30

10
*/