[백준 - 2163번] 초콜렛 자르기 - JAVA 정리 및 해설 (DP방식)

백준 2163번 초콜렛 자르기를 풀어보도록 하겠습니다.

초콜렛 자르기는 사실 쉽게 접근할 수 있습니다. 그저 N*M -1 의 방식으로 푸는게 훨씬 쉽게 풀 수 있는데요.(ㅂㄷㅂㄷ)

저는 이문제의 하단에 보면, 알고리즘 분류의 수학과 "다이나믹 프로그래밍"에 낚여서 이걸 진짜 다이나믹 프로그래밍으로만 생각했습니다. 왜그랬을까요... 덕분에 잠도 못자고 이거 생각해봤네요.

암튼 덕분에 다이나믹 프로그래밍으로도 문제를 풀어서 맞춰서 여기에 어떤 방식으로 풀었는지에 대해서 설명을 해보려합니다.

제가 말하는 cache[][]는 여러분들이 dp[][]로 쓰는 중복 체크를 하기위해 쓴 배열이라고 생각해주시면 됩니다.

0. 가장 중요한건 cache를 -1로 모두 채우고 시작하는 작업이 필요합니다.

1. 일단 우리가 기본적으로 한줄짜리 초콜렛은 무조건 1개짜리를 만들기위해서 그 칸만큼 짤라줘야됩니다.

예를들어 2*1인 경우 1번만 자르면 1*1 이 2개가 나옵니다.  3*1인 경우도 2번만 자르면 1*1이 3개가 나옵니다.

즉, cache[x][1] or cache[1][y] 은 x-1 or y-1을 가져야합니다. 

2.그러니까 값을 가진 cache를 뽑아내려면,  어떤 조각이든간에 1로 만들어주는 작업을 해줘야됩니다. 그래야지 그 값이 튀어 나올거니까요.

저는 어떤 조각이든간에 " 큰 수"를 반으로 쪼개는 작업을 합니다. 

(단, 제가 쪼개려는 수가 홀수면 반으로 쪼개지지 않기때문에, 큰수/2와 큰수 - (큰수/2)로 조각을 따로따로 생각해줍니다.)

그러면 1이되기전까지는 계속 큰수가 반으로든 반에 가깝게 쪼개질 것이므로 결국에는 1이 나오게 될겁니다.

-> 즉, 자기가 원하는걸 찾아서 쪼개는 방식의 dp와 유사합니다. 즉, Top-down 방식인것이죠.

3. 재귀를 통해서 구현하면 땡.  

cache 원래값에 나눠서 작은조각이된 2개의 cache[][]값이 -1인경우면 무조건 제가만든 함수에 다시 넣어서 더하는 역할을 하고 이 값에 +1 을 더하는 것을 해줘야됩니다.

왜냐면 결국 이게 두조각을 쪼개기 위해서 1번을 뚝짜른거기 때문에 +1을 해줘야지 값이 나옵니다.

만약에 이 cache가 -1이 아니면 cache[][]를 리턴하게 끔 만들면 됩니다. (재귀의 중요조건인 재귀 함수의 탈출조건을 만들어주는 겁니다.)

그러면 구현이 됩니다.

제가 푸는 top-down방식 즉, 재귀를 사용하는 dp문제들은 이 폼을 벗어나지 않더라구요.(아직 안푼 dp가 너무 많아서 딱짤라서 단정짓긴 어려운것 같습니다..)

/* 2019.02.05 화 간단한 수학문제 dp로 어렵게 풀어보기  
*/
package codeBaekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class no2163_chocolateDivide {
	static int n,m,cache[][];

	static int div(int x, int y){

		if(cache[x][y] != -1){
			return cache[x][y];
		}
		int d1= 0;
		int d2 = 0;
		if(x>=y){
			d1 = cache[x/2][y];
			d2 = cache[x-(x/2)][y];
			//			System.out.println("check in "+x+" "+y+" "+d1+" "+d2);
			if(d1<0 && d2<0){
				return cache[x][y] = div(x/2, y)+ div(x-(x/2), y)+1;
			}
			else if(d1<0){
				return cache[x][y] = div(x/2, y)+cache[x-(x/2)][y] +1;
			}
			else if(d2<0){
				return cache[x][y] = cache[x/2][y]+ div(x-(x/2), y)+1;
			}
			else{
				return cache[x][y] = cache[x/2][y]+ cache[x-(x/2)][y]+1;
			}
		}
		else{// x<y
			d1 = cache[x][y/2];
			d2 = cache[x][y-(y/2)];
			if(d1<0 && d2<0){
				return cache[x][y] = div(x, y/2)+ div(x, y-(y/2) )+1;
			}
			else if(d1<0){
				return cache[x][y] = div(x, y/2)+cache[x][y-(y/2)] +1;
			}
			else if(d2<0){
				return cache[x][y] = cache[x][y/2]+ div(x, y-(y/2))+1;
			}
			else{
				return cache[x][y] = cache[x][y/2]+ cache[x][y-(y/2)]+1;
			}
		}
		//		System.out.println("체크아웃 "+x+" "+y+"cache"+cache[x][y]);

	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String t = br.readLine();
		StringTokenizer st=  new StringTokenizer (t, " ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		cache = new int [n+1][m+1];
		for(int i=0; i<n+1; i++){
			Arrays.fill(cache[i], -1);
		}
		for(int i =1; i<n+1; i++){
			cache[i][1] = i-1;
		}
		for(int j =1; j<m+1; j++){
			cache[1][j] = j-1;
		}
		div(n,m);
		System.out.println(cache[n][m]);
	}
}
 

이렇게 안푸셔도 됩니다만.. 이문제 덕분에 top-down방식의 t정도는 알게된것 같은 문제라서 감사합니다.