[1일1커밋 9D] 유형별 풀이(2) 이진탐색 대충 끝 | 백준 JAVA 1654, 2805, 2110

지난번에 이어 계속되는 이진 탐색 문제들 풀어보기

 

1654. 랜선 자르기 (실버2) https://www.acmicpc.net/problem/1654

그나저나 이 문제 주인공들 이름이 왜 이럼 출처가 어디문제인가 궁금해지는.. 오영식이와 박성원이~

 

이진 탐색이라고 문제 유형이 정해져있었기에 가능했던 풀이 아닐까 싶다. 아니였음 어떻게 풀지 감도 안잡혔을 듯.

랜선 길이를 최소 1부터 주어진 랜선 길이중 최소값을 맥스로 잡고 (최댓값도 랜선 길이가 될 수 잇음으로) 최댓값을 맥스로 잡고, 필요한 개수가 충족되는 조건으로 이진 탐색을 돌렸다. 이리저리 조건을 수정하고 별거 다했지만 결과는 처참했다.

import java.io.*;
import java.util.*;

public class Main {

	static int k, n;
	static int[] lines;
	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()); // 필요한 
		
		lines = new int[k];
		int max = Integer.MIN_VALUE;
		for(int i=0; i<k; i++) {
			lines[i]=Integer.parseInt(br.readLine());
			max = Math.max(max, lines[i]);
		}
		
		find(1, max, (1+max)/2);
		
		br.close();
	}

	static void find(long s, long e, long mid) {
		
		if(s>e) {
			System.out.println(mid);
			return;
		}
		
		long cnt=0;
		for(int i=0; i<k; i++) cnt += lines[i]/mid;
		
		if(cnt<n) e = mid-1;
		else s = mid+1;
		
		find(s, e, (s+e)/2);
	}
}

 

하...... 내 코드가 도저히 어디가 틀린건지도, 다른 사람들과 어느 부분이 다른건지 도저히 모르겠지만 안된다... 참고로 내가 봤던 답안은 https://thsd-stjd.tistory.com/70 요기인데 나랑 똑같은 코드 아닌가????? 열받아서 포기함

++) 지금 보니 포스팅은 21년도 글이고, 그 뒤로 테스트케이스가 추가된듯하다. 해당 블로그 코드로 제출해도 런타임 오류남(/ by zero)

 

재귀를 포기하고 결국 성공

import java.io.*;
import java.util.*;

public class Main {

	static int k, n;
	static int[] lines;
	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()); // 필요한 
		
		lines = new int[k];
		int max = Integer.MIN_VALUE;
		for(int i=0; i<k; i++) {
			lines[i]=Integer.parseInt(br.readLine());
			max = Math.max(max, lines[i]);
		}
		
		long s = 1;
		long e = max;
		long mid = (s+e)/2;
		long cnt=0;
		while(s<=e) {
			mid = (s+e)/2;
			cnt=0;
			for(int i=0; i<k; i++) cnt += lines[i]/mid;
			if(cnt<n) e=mid-1;
			else s=mid+1;
		}
		System.out.println(e);
		
		br.close();
	}
}

지금까지 랜선 길이의 답은 mid라고 생각했는데 mid로 출력하면 틀리고 e(이진탐색 최댓값)으로 해야 통과이다.

이유는 여전히 모르지만 추측되는 건.. 아래 내가 찾은 반례이다.

4 9
10
9
8
8

랜선 길이가 4인 경우 랜선이 8개 나오고, 3인 경우 10개가 나온다. 9개 이상이 나와야하기 때문에 답은 3이다. 하지만 mid로 답을 구하게되면 4가 나온다.

랜선이 꼭 N개가 안되는 경우 N개 이상도 가능하다는 점과 다음 로직에 사용할 s와 e를 구하는 부분과 mid를 구하는 부분 이런 조건들이 합쳐져 답이 mid가 아닌 e가 되는 듯 한데, 이 문제에 너무 시간을 많이 잡아먹어서 이해하고싶지 않다 이제...

내 코드에서 이상한 점 있다면 알려주세여..

 

++) 다시 보니 반복문을 돌며 찍어보면

s=1 e=10 mid=5 cnt=5
s=1 e=4 mid=2 cnt=17
s=3 e=4 mid=3 cnt=10
s=4 e=4 mid=4 cnt=8

여전히 봐도 이해가 잘 안감

 

2805. 나무 자르기 (실버2) https://www.acmicpc.net/problem/2805

위의 문제와 아주 유사한 문제

import java.io.*;
import java.util.*;

public class Main {

	static int n, m;
	static int[] trees;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken()); // 나무의 수 (1 ≤ N ≤ 1,000,000)
		m = Integer.parseInt(st.nextToken()); // 집으로 가져가려는 나무의 길이 (1 ≤ M ≤ 2,000,000,000)
		trees = new int[n];
		st = new StringTokenizer(br.readLine());
		int idx = 0;
		int min = Integer.MIN_VALUE;
		int max = Integer.MIN_VALUE;
		while(st.hasMoreTokens()) {
			trees[idx]=Integer.parseInt(st.nextToken());
			max = Math.max(max, trees[idx]);
			min = Math.min(min, trees[idx]);
			idx++;
		}
		
		long start = 0; // 절단기 높이 0 이상 
		long end = max;
		long mid = (start+end)/2;

		long total;
		while(start<end) {
			total=0;
			mid = (start+end)/2;
			for(int i=0; i<n; i++) {
				if(trees[i]>mid) total += (trees[i]-mid);
			}
		
			if(total>=m) start=mid+1; 
			else end=mid;
		}
		System.out.println(start-1);
		
		br.close();
	}
}

후 이번엔 또 while 반복문에서 등호가 빠지고 조건문에는 등호가 들어가고 반환값은 또 start-1이고.. 난리다. 이진탐색이 이렇게 어려운 알고리즘인가

 

더 이상 풀고싶지 않지만 마지막으로 골드 문제 하나만 도전해보고 이진탐색 때려칠거다.

 

2110. 공유기 설치 (골드4) https://www.acmicpc.net/problem/2110

import java.io.*;
import java.util.*;

public class Main{

	static int n, c;
	static int[] x; // 집의 좌표 
	static long ans;
 	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken()); // 집의 개수 
		c = Integer.parseInt(st.nextToken()); // 공유기 개수
		x = new int[n];
		for(int i=0; i<n; i++) {
			x[i]=Integer.parseInt(br.readLine());
		}
		Arrays.sort(x);
		
		// 가능한 거리 1 ~ 집 좌표 사이 최대 거리 
		long min = 0;
		long max = x[n-1]-x[0];
		long mid;
		
		int cnt; // 공유기 수
		int loc;
		while(min<=max) {
			cnt = 1; // 설치 대수, 첫번째 집 설치  
			loc = x[0]; // 설치 위치, 첫번째 집 먼저 
			mid = (min+max)/2;
			for(int i=1; i<n; i++) {
				if(x[i] >= mid+loc) {
					// x[i] 다음 집의 위치 >= mid+loc 다음 공유기 설치 위치 
					cnt ++;
					loc = x[i];
				}
			}
			
			if(cnt>=c) {
				ans = mid;
				min = mid+1; // 계획보다 많음으로 간격을 늘림
			}
			else {
				max = mid-1; // 계획보다 적음으로 간격을 줄
			}
		}
		System.out.println(ans);
		
		br.close();
	}
}

예전같았음 엄두도 못냈을 문제인데 문제 유형을 연습하고 보니 어느정도 눈에 들어오는 것 같다.

사실 혼자 힘으로 풀진 못하고 다른 블로그 참고하였는데 이전 문제들처럼 반환값을 min, max로 하는 것 보다 저렇게 중간에 이게 답이다! 하고 result에 mid 값을 담아 반환하는게 더 올바른 코드인 것 같다. 해당 방법으로 위의 소스들도 한번 수정해봐야겠다.

 

원래는 월요일에 공부하고 올렸어야하나 밀리고 밀려 화요일 저녁이 되어서야 올리는 포스팅.. 끝!@