[JAVA] 11066 파일 합치기

안녕하세요. 또 1주일간 정신을 놓고 다녀서..이제 다시 문제 풀이 포스팅을 시작하네요 허허

그래도 시작이 반이라는 말이 있으니까 기죽지 말고 또 열심히 해보겠습니다 : ) 

 

이번 문제는

 

https://www.acmicpc.net/problem/11066

11066번: 파일 합치기

 

분명 민경하 교수님은 '다이나믹 프로그래밍 문제가 나오면 땡큐지' 라고 하셨는데, 저는 1도 공감이 가지 않았던 문제입니다. 교수님 죄송..

 

-나의 풀이-

 

문제를 이해하는데 시간이 무척이나 오래걸렸습니다. 저의 볼품없는 집중력이 주된 원인이라고 생각됩니다.

머리속 생각의 고리를 끝까지 이어나가서 결론을 내려야하는데, 저는 생각을 깊게 안해서 수박겉핣기 식으로 문제를 풀라고 하는 아주 나쁜 습관이 있다는 것을 알았습니다. 자책은 그만하고 진짜 문제를 풀어 보겠습니다. 

 

문제를 읽어 보신다면, 역시나 최소비용을 구하는 문제임을 알 수 있습니다. 최소비용이라 하면 결국 모든 케이스를 다 확인을 해야합니다. 그렇다면 어떤 방식으로 모든 케이스를 다 확인해야하는지가 해결 포인트겠군요. 

 

모든 케이스를 다 확인하는 알고리즘은 제가 배움이 깊지않아서 4개 정도가 전부입니다. 

 

1. 브루트 포스 

2. 그리디 

3. 디피 

4. 그래프 탐색

 

하지만 문제에서 주어진 조건을 보면 테스트 케이스가 1개 이상으로 주어지기 때문에 디피를 이용하는 것이 좋을것 같다고 생각 했습니다. 

 

디피를 구현할 때 민영하 교수님은 점화식을 꼭 세우라고 하셨습니다. 

문제 상황을 직접 써보며 생각해보면, 점화식을 세워볼 수 있습니다. 

 

 

1. 연속되는 값들만 합할수있다. 

결국 어떤 케이스라도 연속되는 범위의 값이 합쳐져서 비용을 구해야합니다. 당연한 이야기로 생각할 수 있지만 저는 머리가 좋은편이 아니라 확실하게 집고 이해하고 가야 안심이 됩니다. 

 

2. 연속되는 범위를 기준으로 생각하면 memorization을 가능하다. 

모든 케이스를 다 확인해야하니, 특정 범위를 여러번 구해야 할 경우가 있을 것 입니다. 즉 memoziation을 이용한다면 시간을 줄일 수 있을 것입니다. (물론 범위이니 2차원 배열에 담아야합니다 평범한 배낭에서 해봤쓰)

 

여기까지 점화식을 세우자면

Dp(1,n) = Math.min(DP(1,i)+DP(i+1,n),..,DP(1,n-1)+DP(n,n))) 

(int i=1 ; i<n , i++)

이런 형식이 된다는 것을 알 수 있습니다. 

 

 

점화식을 세우고 코드를 구현하다 보면, 골치아픈 부분이 하나 있습니다.  비용을 구하는 부분에서...그..그림으로 하겠읍니다.

 

그래도 이해가..어려워 보이넵

제가 한 실수인데, 특정 범위를 만드는 비용과 그 뭉치의 요소의 합이 늘 같지는 않아서 따로 분리를 해줘야합니다. 

예로 2,4를 합치는데 2+4 = 6으로 같지만 2,4,3은 2+4+6+3= 15로 차이가 납니다. 

그러니 멍충이같이 비용만으로 계산한다던가, 소수의 케이스인 비용과 요소의 합이 같다는 것을 이용하여 2를 곱해주면 안됩니다. 아 여기서 멍충이는 저입니다. 

 

그래서 생각해낸 방법이 memoziation을 두개로 구분하였습니다. 

 

1. cost[ ] [ ] 

> 합치는 비용만 저장

2. sumValue[ ] [ ]

> 범위 내 원소의 합을 저장 

 

이렇게 나누면 쉽고 이쁘게 구현을 할 수 있습니다.

 

-코드 

import java.io.*;
import java.util.Arrays;
public class Main {
	static int[][] cost,sum;
	public static int dp(int[] nums,int sp, int ep) {
		if(sp+1 == ep) {
			 cost[sp][ep]=(nums[sp]+nums[ep]);
			 return cost[sp][ep];
		}
		if(ep==sp) {
			return  cost[sp][ep] = 0;
		}
		if(cost[sp][ep]!=Integer.MAX_VALUE) {
			return cost[sp][ep];
		}
		for(int i=sp; i<ep; i++) {
			cost[sp][i] =dp(nums,sp,i);
			cost[i+1][ep] =dp(nums,i+1,ep);
			cost[sp][ep] = Math.min(cost[sp][i]+cost[i+1][ep]+sumValue(nums,sp,i)+sumValue(nums,i+1,ep),
					cost[sp][ep]);
		}
		return cost[sp][ep];
	}
	public static int sumValue(int[] nums, int sp, int ep) {
		if(sum[sp][ep]!=0) {
			return sum[sp][ep];
		}
		int answer = 0;
		for(int i=sp;i<=ep;i++) {
			answer+=nums[i];
		}
		return sum[sp][ep]=answer;
	}
	public static void reset() {
		for(int i=0; i<cost.length; i++) {
			Arrays.fill(cost[i], Integer.MAX_VALUE);
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int testCase = Integer.parseInt(bf.readLine());
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<testCase;i++) {
			int size = Integer.parseInt(bf.readLine());
			int[] nums = new int[size+1];
			String[] tmps = bf.readLine().split(" ");
			for(int j=0; j<size; j++) {
				nums[j+1] = Integer.parseInt(tmps[j]);
			}
			cost = new int[size+1][size+1];
			sum = new int[size+1][size+1];
			reset();
			dp(nums,1,size);
			sb.append(cost[1][size] +"\n");
			
		}
		System.out.println(sb);
	}
	

}

 

- 생각해볼 것

1. memoziation의 탑다운 과 바텀업 형식

2. 메모리 관리에 대해

 

- 후기 

1. 디피는 점화식이라고 하셨다.

2. 그렇다고 하신다..

3. 그래도 땡큐는 아니다ㅠ