글 읽기 - 어떤 예외가 있을 까요..?

petermoon12 8년 전 0

DP로 어떻게 접근해야하는지 생각이 나지 않아서, 정렬 후에 다음항과 비교하여 차이가 작은 값을 더해나갔는데..

어떤 예외가 존재하는지 모르겠습니다.

DP로는 어떻게 풀 수 있을까요...ㅜ

package feb11.makecouple;

import java.util.Scanner;

public class Main {

	
	public static void selectionSort(int[] arr){
		
		for(int i = 0; i < arr.length; i++){
			
			int minIndex = i;
			for(int j = i; j < arr.length; j++){
				
				if(arr[j] < arr[minIndex])
					minIndex = j;
			}
			int temp = arr[minIndex];
			arr[minIndex] = arr[i];
			arr[i] = temp;
		}
	}
	
	public static void sum(int[] arr1, int[] arr2){
		
		long sum = 0;
		int gap = arr1.length - arr2.length;
		
		int now = 0;
		for(int i = 0; i < arr2.length; i++){

			if (gap > 0) {
				
				while(now < arr1.length - 1){
					
					int g1 = Math.abs(arr2[i] - arr1[now]);
					int g2 = Math.abs(arr2[i] - arr1[now + 1]);

					if (g1 < g2) {
						sum += g1;
						now++;
						break;
					} else {
						gap--;
						now++;
						if(gap == 0){
							sum += g2;
							now++;
							break;
						}
					}
				}
			}
			else {
				sum += Math.abs(arr2[i] - arr1[now++]);
				System.out.println(sum);
			}
		}
		
		System.out.println(sum);
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n, m;
		int[] arr_n, arr_m;
		
		n = sc.nextInt();
		m = sc.nextInt();
		
		arr_n = new int[n];
		arr_m = new int[m];
		
		for(int i = 0; i < n; i++)
			arr_n[i] = sc.nextInt();
		
		for(int i = 0; i < m; i++)
			arr_m[i] = sc.nextInt();

		selectionSort(arr_n);
		selectionSort(arr_m);
		
		if(n > m)
			sum(arr_n, arr_m);
		else
			sum(arr_m, arr_n);
		
		sc.close();
	}
}

chatterboy 8년 전 0

항상 n >= m이라고 한다면, m명의 커플을 무조건 만들어야 합니다.

따라서, 점화식을 세워본다면

T[i][j] = a[1...i]와 b[1...j]를 고려했을 때, 최적값이라고 한다면 ( 1<=i<=n, 1<=j<=m )

T[i][j] = min(T[i-1][j], T[i-1][j-1] + |a[i]-b[j]|)

로 나타낼 수 있습니다.

여기서 항상 m명을 뽑았는지에 대한 처리만 해주시면 가능합니다.

petermoon12 8년 전 0

음.. 우선 답변 감사드립니다ㅠ

그런데 점화식을 봐도 잘 이해가 되지 않습니다.

T배열에 저장하는 것이랑 제가 했던 바와 같이 sum변수에 저장해나가는 것 하고 무슨 차이가 있을까요..ㅜ?

어차피 정렬된 상태인데요...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어떤 예외가 있을 까요..?

petermoon12 8년 전 0

chatterboy 8년 전 0

petermoon12 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말