백준 18113 - (Java)그르다 김가놈

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

18113번: 그르다 김가놈

1. 유형

이분탐색

 

2. 문제 접근

 

이 문제는 이분탐색 문제입니다. 

 

저는 맨 처음 문제를 잘못이해서 계속 틀렸습니다. 

"김밥 길이가 K cm이거나 그보다 짧으면 그 김밥은 폐기한다." 이 부분에 조심해야 됩니다.

 

만약 첫번째 테스트 케이스에서 김밥길이 13이 들어올 경우, K=6일때

양쪽을 자르고 남은 길이는 1입니다. 이 길이는 위의 조건 때문에 폐기 해버리는 걸로 착각했습니다.

 

하지만 2K이상이면 무조건 배열에 포함시켜주고, 위 조건은 2K이하 일때만, 해당하는 조건인거 같습니다.

 

"2K cm보다 짧아서 한쪽밖에 자르지 못한다면, 한쪽만 꼬다리를 잘라내고, 남은 김밥 길이가 K cm이거나 그보다 짧으면 그 김밥은 폐기한다."

 

위 처럼 바꾸는게 맞는거 같습니다.

 

아무튼, 계속 풀이하면

 

1. start, end를 설정

2. mid를 이용해서 김밥이 몇개 만들어지는지 카운트

3. 카운트한게 M이상이면 조건 만족

 

위를 이분탐색으로 start>end가 될때까지 진행합니다.

 

끝.

 

3. 코드

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

public class Main {
	static int N, K, M;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = stoi(st.nextToken());
		K = stoi(st.nextToken());
		M = stoi(st.nextToken());
		List<Integer> list = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			int gb = stoi(st.nextToken());
			if (gb > (2 * K))
				list.add(gb-(2*K));
			if(2*K > gb && gb>K)
				list.add(gb-K);				
		}
		int start = 1, end = 1000000000;
		int ans = -1;
		while (start <= end) {
			int mid = (start + end) / 2;
			int count = calc(list, mid);
			if (count >= M) {
				ans = mid;
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}
		System.out.println(ans);
	}

	static int calc(List<Integer> list, int mid) {
		int sum = 0;
		for (int k : list) {
			sum += (k / mid);
		}
		return sum;
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}