[알고리즘] 파일 합치기

파일 합치기

11066번: 파일 합치기

해결 방법

연속된 행렬 곱셈 푸는 문제와 많이 비슷한 문제인 것 같아서 dp로 풀어줘야 한다.

dp[i][j]는 i에서 j까지 합쳤을 때 가장 짧은 최소값이라고 정의를 내리고 시작했다.

다이나믹으로 풀기 위해서는 작은 것부터 구하면서 점점 크게 나가야 한다.

 

문제의 예시

files	0	1	2	3
value	40	30	30	50

 

여기서 2차원 배열을 이용해서 dp[files.size()][files.size()]를 만들어 준다. (혹은 1칸 늘려서 0을 비우면서도 가능)

 

1) 1개를 먼저 합치는 경우(따로 초기화)

0~1를 합쳤을 경우 dp[0][1] = 0번째 file + 1번째 file = 40 + 30 = 70

1~2를 합쳤을 경우 dp[1][2] = 1번째 file + 2번째 file = 30 + 30 = 60

2~3를 합쳤을 경우 dp[2][3] = 2번째 file + 3번째 file = 30 + 50 = 80

위치	0	1	2	3
0	0	70
1	0	0	60
2	0	0	0	80
3	0	0	0	0

2) 2개를 합치는 경우 

0~2를 합쳤을 경우

dp[0][2] =min(0~1를 합친 것+ 2번째 합쳤을 경우, 0번째 + 1~2를 합쳤을 경우)

 

1~3를 합쳤을 경우

dp[1][3] = min(1~2를 합친 것+ 3번째 합쳤을 경우, 1번째 + 2~3를 합쳤을 경우)

 

3) 3개 합쳤을 경우 

0~3를 합쳤을 경우

dp[0][3] = min(0번째+(1~3) , (0~1)+(2~3), (0~2)+(3번째))  //

 

 

여기서 2)경우와 3)경우에서는 마지막에 합쳤을 경우는 해당 구간의 전체 합을 더하는 경우와 동일 하다

(예로들면 0~2를 합칠 때 dp[0][0]+dp[1][2]+(0에서 2까지의 원소들의 합) or dp[0][1]+dp[2][2]+(0에서 2까지의 원소들의 합))

 

 

이렇기 때문에 원소들의 합 배열을 미리 만들어 준다( for문으로 합산을 구할 수 있지만 파일이 많아질수록 연산시간이 길어지게 되기 때문)

 

변수  : sumFiles[i] : 0번째부터 i번째까지의 합

sumFiles	0	1	2	3
value	40	70 (sumFiles[0]+files[1])	100 (sumFiles[1]+files[2])	150 (sumFiles[2]+files[3])

ex) 0번째부터 n번째의 합 : sumFiles[n]

     n번째부터 m번째의 합 : sumFiles[m]-sumFiles[n]

 

2)와 3)의 경우의 식

dp[i][j] : i부터 j번까지의 최솟값

for (int k = i; k < j; k++) {
	if (dp[i][j] == 0)
		dp[i][j] = dp[i][k] + dp[k + 1][j] + (i~j까지의 합계);
	else
		dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + (i~j까지의 합계));
}

 

반복문을 통해 dp를 접근하는 순서를 알아야 한다.

위치	0	1	2	3
0	0	70	첫번째 루프	두번째 루프
1	0	0	60	첫번째 루프
2	0	0	0	80
3	0	0	0	0

접근 순서는 

dp[0][2] -> dp[1][3] 

dp[0][3]

이렇게 된다. (오른쪽 아래 방향으로 대각선으로 접근함)

시작할 때는 열은 행+2라고 볼수 있다.

i를 행 j를 열이라고 하면 초기값을 i=0, j=2

for (int j = 2; j < files.size(); j++) {  //열
	for (int i = 0; i+j < files.size(); 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] + sumDistance(i, i+j, sumFiles);
			else
				dp[i][i+j] = Math.min(dp[i][i+j], dp[i][k] + dp[k + 1][i+j] + sumDistance(i, i+j, sumFiles));
		}
	}
}

이렇게 풀어나간다.

 

소스코드

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int testCase = Integer.parseInt(br.readLine());
		for (int i = 0; i < testCase; i++) {
			int N = Integer.parseInt(br.readLine());
			String str = br.readLine();
			st = new StringTokenizer(str);
			List<Integer> list = new ArrayList<>();
			for (int j = 0; j < N; j++)
				list.add(Integer.parseInt(st.nextToken()));

			merge(N, list);
		}

	}

	static Integer sumDistance(int i, int j, List<Integer> sumFiles) {
		if (i == 0)
			return sumFiles.get(j); // 시작 부분이 처음일 때는 j까지만
		else
			return sumFiles.get(j) - sumFiles.get(i-1); // i~j구간의 합만큼의 합산
	}

	static void merge(int num, List<Integer> files) {
		int[][] dp = new int[files.size()][files.size()];
		
		List<Integer> sumFiles = new ArrayList<>();
		
		sumFiles.add(files.get(0));
	
		for (int i = 1; i < files.size(); i++)  // 0부터 N까지의 합계를 구함
			sumFiles.add(files.get(i) + sumFiles.get(i - 1));
		

		for (int i = 0; i < files.size() - 1; i++) // (1,2)(2,3)(3,4) 등 합쳐지는 것 초기화
			dp[i][i + 1] = files.get(i) + files.get(i+ 1);
		
		
		for (int j = 2; j < files.size(); j++) {
			for (int i = 0; i+j < files.size(); 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] + sumDistance(i, i+j, sumFiles);
					else
						dp[i][i+j] = Math.min(dp[i][i+j], dp[i][k] + dp[k + 1][i+j] + sumDistance(i, i+j, sumFiles));
				}
			}
		}
		System.out.println(dp[0][files.size() - 1]);
	}
}

 

문제가 어려워서 다른 사람의 풀이법도 많이 참고했다.

https://blog.naver.com/tjdwns0920/221135677693