[알고리즘] 이분 탐색 문제 풀이(백준 2805번, 1654번, 2512번)

1. 나무 자르기(백준 2805번)

 

2805번: 나무 자르기 (acmicpc.net)

2805번: 나무 자르기

 

▷ 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class CutTree {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		String inputArr[] = br.readLine().split(" ");
		
		int n = Integer.parseInt(inputArr[0]);
		
		int m = Integer.parseInt(inputArr[1]);
		
		List<Integer> inputList = new ArrayList<>();

		int min = 0;
				
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		while(st.hasMoreTokens()) { 
			inputList.add(Integer.parseInt(st.nextToken()));
	    }
		
		int max = Collections.max(inputList);
		
		while(min < max) {
			int mid = (min+max)/2;
						
			long sum = 0;
			
			for(int tree : inputList) {
				if(tree-mid > 0) {
					sum += (tree-mid);					
				}
			}
			
			if(sum >= m) {
				min = mid+1;
			} else {
				max = mid;
			}
		}
		
		System.out.println(min - 1);
	}
}

 

 

2. 랜선 자르기(백준 1654번)

 

1654번: 랜선 자르기 (acmicpc.net)

 

▷ 풀이 코드

1. 풀이 1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CutLan {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
	
		String inputArr[] = br.readLine().split(" ");
		
		int k = Integer.parseInt(inputArr[0]);
		
		int n = Integer.parseInt(inputArr[1]);
		
		List<Integer> inputList = new ArrayList<>();

		for(int i=0; i<k; i++) {
			inputList.add(Integer.parseInt(br.readLine()));
		}
				
		long max = Collections.max(inputList);
		
		max++; 
		
		long min = 0;
		
		while(min < max) {
			long mid = (min+max)/2;
			
			long sum = 0;
			
			for(int lan : inputList) {
				sum += (lan/mid);
			}
			
			if(sum < n) {
				max = mid;
			} else {		
				min = mid +1;
			}
		}
	
		System.out.println(min - 1);			
		
	}
}

2. 풀이2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CutLan2 {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
	
		String inputArr[] = br.readLine().split(" ");
		
		int k = Integer.parseInt(inputArr[0]);
		
		int n = Integer.parseInt(inputArr[1]);
		
		List<Integer> inputList = new ArrayList<>();

		for(int i=0; i<k; i++) {
			inputList.add(Integer.parseInt(br.readLine()));
		}
				
		long max = Collections.max(inputList);
		
		long min = 1;
		
		while(min <= max) {
			long mid = (min+max)/2;
			
			long sum = 0;
			
			for(int lan : inputList) {
				if(mid == 0) break;
				sum += (lan/mid);
			}
			
			if(sum < n) {
				max = mid -1;
			} else {		
				min = mid +1;
			}
		}
	
		System.out.println(max);			
		
	}
}

3. 풀이3

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CutLan3 {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
	
		String inputArr[] = br.readLine().split(" ");
		
		int k = Integer.parseInt(inputArr[0]);
		
		int n = Integer.parseInt(inputArr[1]);
		
		List<Integer> inputList = new ArrayList<>();

		for(int i=0; i<k; i++) {
			inputList.add(Integer.parseInt(br.readLine()));
		}
				
		long max = Collections.max(inputList);
		
		long min = 0;
		
		while(min < max) {
			long mid = (min+max)/2;
			
			long sum = 0;
			
			for(int lan : inputList) {
				if(mid == 0) break;
				sum += (lan/mid);
			}
			
			if(sum < n) {
				max = mid;
			} else {		
				min = mid +1;
			}
		}
		
		if(min == 0) {
			System.out.println(1);
		} else if(Collections.max(inputList) == Collections.min(inputList) && k==n) {
			System.out.println(Collections.max(inputList));
		} else {
			System.out.println(min -1);			
		}
		
	}
}

 

 

3. 예산(백준 2512번)

 

2512번: 예산 (acmicpc.net)

2512번: 예산

 

▷ 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Budget {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
	
		int n = Integer.parseInt(br.readLine());
				
		List<Integer> inputList = new ArrayList<>();

				
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int tmpSum = 0;
		
		while(st.hasMoreTokens()) { 
			int input = Integer.parseInt(st.nextToken());
			inputList.add(input);
			
			tmpSum += input;
	    }
		
		int max = Collections.max(inputList);
		
		int min = 0;
		
		int m = Integer.parseInt(br.readLine());

		if(tmpSum <= m) {
			System.out.println(max);
		} else {
			while(min < max) {
				int mid = (min+max)/2;
				
				long sum = 0;
				
				for(int money : inputList) {
					if(money > mid) {
						sum += mid;
					} else {
						sum += money;					
					}
				}
				
				if(sum > m) {
					max = mid;
				} else {		
					min = mid +1;
				}
			}
			
			System.out.println(min -1);			
		}
		
	}
}

 

 

이번에는 알고리즘 스터디에서 공부했던 이분 탐색을 통해 백준 문제 풀이를 해보았습니다!!

 

탐색법에 대한 공부를 해보니 필요 없는 경우의 수를 줄이면서 원하는 결과 값을 찾을 수 있네요

 

동일한 문제를 어떤 방법으로 풀이하는 것이 최선인지 찾아가는 방법이 중요한 것 같아요!

 

더 다양한 문제들을 풀어보면서 문제 풀이 방법들에 대해서 익혀볼게요~

 

많은 분들의 피드백은 언제나 환영합니다!  많은 댓글 부탁드려요~~