백준 1654. 랜선 자르기

🅰 백준 1654. 랜선 자르기

1654번: 랜선 자르기

✏️ 문제 풀이

• 나무자르기와 마찬가지로 이분탐색을 이용하여 정답이 되는 값을 도출해내는 문제이다.
• start값을 1로 설정해주는게 중요하다. 또한 end값을 N개의 랜선 중 최고 길이의 값, mid = (start+end)/2 로 설정해주었다.
• 재귀함수의 기저조건으로 start>end 이면 결과값을 출력해주었고
• for문안에서 각 랜선 / mid를 정수형으로 변환하여 cnt에 더해주었다.
• height값과 N을 비교하여 cnt>=N이면 start와 mid값을 최신화시켜주었고
• cnt<N이면 end와 mid값을 최신화시켜줘서 재귀를 반복해주었다.

✏️ 소스코드

package binarysearch;

import java.util.*;
import java.io.*;
/*이분탐색을 이용하여 가능한 케이스들을 탐색하면서 정답을 찾았다.
 * start, end, mid 값을 설정해주는 과정이 어려웠다.*/
public class Main_실버3_1654_랜선자르기 {
	private static long lan[];
	private static int K, N;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		K = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		lan = new long[K];
		long max = 0;
		for (int i = 0; i < K; i++) {
			lan[i] = Integer.parseInt(br.readLine());
			if(max<lan[i]) max = lan[i];
		}
		long start = 0;
		long end = max;
		long mid = (start+end)/2;
	
		
		recur(start, mid, end);
	}

	private static void recur(long start, long mid, long end) {
		if (start > end) {
			System.out.println(mid);
			return;
		}
		int cnt = 0;
		for (int i = 0; i < K; i++) {
			cnt += (long) lan[i] / mid;
		}
		if (cnt < N) {
			end = mid - 1;
			mid = (start + end) / 2;
		} else if (cnt >= N) {
			start = mid + 1;
			mid = (start + end) / 2;
		}
		recur(start, mid, end);
	}
}

 

✅ 후기

• 나무자르기와 거의 유사한 문제라 쉽게 풀 수 있었다. 한번 공부한 유형은 다음에도 잘 적용할 수 있도록 꾸준히 복습해야겠다.