[백준] 2885 초콜릿 식사 - 분할정복(DivideAndConquer) JAVA

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

코드설명

분할정복(DivideAndConquer)을 활용합니다.

 

문제를 풀고나서 태그를 확인해보니, 수학, 그리디, 구현문제였습니다.

제가 분할정복이라하고 구현했지만, 사실상 코드로직은 분할정복에서 차용했지만, 그저 DFS로 구현한것이나 다름없습니다.

 

문제에서 틀렸었던점은 기저사례입니다.

항상 하던대로 분할정복에서는 기저사례로 이렇게 한개가 되면 종료되도록 처리했는데, 이렇게 할경우 초콜릿의 가장 작은 단위가 되었기에 K -=1 을 해주어야하지만 해당 로직 처리가 좀 복잡해집니다.

즉, 초콜릿이 1줄 남았다면 바로 종료처리를 했는데 생각해보면 1개가 남았더라도 초콜릿의 크기를 줄여주어야 합니다.

항상 하던대로 처리하면 안되고, 문제의 조건에 따라 처리해야 합니다.

if(lo == hi) {
    return 0;
}

 

그리고 아직 초콜릿의 크기가 남은경우에만 분할정복을 계속해서 진행합니다.

		if(K>0) ret = divideAndConquer(lo, mid) + 1;
		if(K>0) ret = divideAndConquer(mid + 1, hi) + 1;

 

그리고 가장 중요한점은 초콜릿의 Size를 짜르고서 divideAndConquer가 아닌 

해당 함수에서 바로 현재 초콜릿 Size만큼을 확인하는 것 입니다.

만약 현재 Size의 함수에서 초콜릿의 개수를 채울 수 있다면 채우고 이미 그 부분 초콜릿은 모두 사용했으니 멈추는 것이지요.

만약, K보다 Size가 크다면 초콜릿을 한번 더 잘라주어야 하고요.

		if(K >= (hi - lo + 1)) {
			K -= (hi - lo + 1);
			return ;
		}else {
			answer += 1;
		}

 

그리고 초콜릿을 자르면 2가지로 나눠지겠지요.

		if(K>0) divideAndConquer(lo, mid);
		if(K>0) divideAndConquer(mid + 1, hi);

 

 

그리고 좀 개선시켜야할 부분은 초콜릿의 최소 크기를 구하는 방식입니다.

아래와 같이 좀 범위를 직접 구해서 처리했습니다.

int chocolateSize = 0;
for(int i=0; ; i++) {
    int left = 1 << i;
    int right = 1 << (i + 1);

    if(K == left) {
        chocolateSize = left;
        break;
    }
    else if(K > left && K < right) {
        chocolateSize = right;
        break;
    }
}

 

 

하지만 아래와 같이 K보다 크거나 같을떄까지 chocolateSize << 1 를 1씩 Shifting 하면 됩니다.

 

int chocolateSize = 1;
while(chocolateSize < K) {
    chocolateSize = chocolateSize << 1;
}

 

코드

가장 직관적이고, 맘에 드는 코드입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, P, K, A, B, X, R, T;
	static int answer = 0;
	static int[] arr;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		K = Integer.parseInt(st.nextToken());
		
		int chocolateSize = 0;
		for(int i=0; ; i++) {
			int left = 1 << i;
			int right = 1 << (i + 1);
			
			if(K == left) {
				chocolateSize = left;
				break;
			}
			else if(K > left && K < right) {
				chocolateSize = right;
				break;
			}
		}
		
		
		System.out.print(chocolateSize+" ");
		divideAndConquer(0, chocolateSize - 1);
		System.out.println(answer);
	}
	
	static void divideAndConquer(int lo, int hi) {

		//반으로 자릅니다.
		int mid = (lo + hi) / 2;
		if(K >= (hi - lo + 1)) {
			K -= (hi - lo + 1);
			return ;
		}else {
			answer += 1;
		}
		
		if(K>0) divideAndConquer(lo, mid);
		if(K>0) divideAndConquer(mid + 1, hi);
		
		return ;
	}
	
}

 

 

1번 코드와 유사하나, 코드가 깔끔하지 않습니다.

answer값을 갱신시켜서 몇 번 초콜릿을 자르는지 구합니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, P, K, A, B, X, R, T;
	static int answer = 0;
	static int[] arr;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		K = Integer.parseInt(st.nextToken());
		
		int chocolateSize = 0;
		for(int i=0; ; i++) {
			int left = 1 << i;
			int right = 1 << (i + 1);
			
			if(K == left) {
				chocolateSize = left;
				break;
			}
			else if(K > left && K < right) {
				chocolateSize = right;
				break;
			}
		}
		
		
		System.out.print(chocolateSize+" ");
		divideAndConquer(0, chocolateSize - 1);
		System.out.println(answer);
	}
	
	static int divideAndConquer(int lo, int hi) {
//		if(lo == hi) {
//			return 0;
//		}
		
		int ret = 0;
		//반으로 자릅니다.
		int mid = (lo + hi) / 2;
		if(K >= (hi - lo + 1)) {
			K -= (hi - lo + 1);
			return 0;
		}else {
			ret = 1;
		}
		
		if(K>0) ret = divideAndConquer(lo, mid) + 1;
		if(K>0) ret = divideAndConquer(mid + 1, hi) + 1;
		
		return ret;
	}
	
}

 

세번쨰 코드입니다.

아래 코드의 경우 int 형을 반환하도록 처리하여 ret값을 반환하도록 처리했습니다.

이유는 초콜릿을 한번 자르면 2개의 초콜릿으로 나눠지기에 아래 로직과 직관적인 로직이 맞지 않아 헷갈리지만 if(K>0)이 있기에 작동합니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, P, K, A, B, X, R, T;
	static int answer = 0;
	static int[] arr;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		K = Integer.parseInt(st.nextToken());
		
		int chocolateSize = 0;
		for(int i=0; ; i++) {
			int left = 1 << i;
			int right = 1 << (i + 1);
			
			if(K == left) {
				chocolateSize = left;
				break;
			}
			else if(K > left && K < right) {
				chocolateSize = right;
				break;
			}
		}
		
		
		System.out.print(chocolateSize+" ");
		System.out.println(divideAndConquer(0, chocolateSize - 1));
//		System.out.println(answer);
	}
	
	static int divideAndConquer(int lo, int hi) {
//		if(lo == hi) {
//			return 0;
//		}
		
		int ret = 0;
		//반으로 자릅니다.
		int mid = (lo + hi) / 2;
		if(K >= (hi - lo + 1)) {
			K -= (hi - lo + 1);
			return 0;
		}
		
		if(K>0) ret = divideAndConquer(lo, mid) + 1;
		if(K>0) ret = divideAndConquer(mid + 1, hi) + 1;
		
		return ret;
	}
	
}