BOJ 백준온라인져지 14627 파닭파닭 풀이

1. 이분 탐색

2. 내 코드에서는 tempC 같은 역할을 해주는 변수가 없으면 풀지 못한다.

3. 다른 풀이들은 확인해보지 않음.

4. tempC 는 파 하나로 여러 개의 닭에 나눠넣는 것을 확인하는 변수

	import java.util.*;
	import java.io.*;
	/**
	* https://www.acmicpc.net/problem/14627
	* BOJ 백준온라인져지 14627 파닭파닭 풀이
	*/
	public class Main {
	private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String str1[] = br.readLine().split(" ");
	int S = Integer.parseInt(str1[0]);
	int C = Integer.parseInt(str1[1]);
	int arr[] = new int[S];
	for (int i = 0; i < S; i++) {
	arr[i] = Integer.parseInt(br.readLine());
	}
	Arrays.sort(arr);
	int l = 1;
	int r = arr[S - 1];
	long result = 0;
	while (l <= r) {
	int mid = (l + r) / 2;
	long tempSum = 0;
	int tempC = C;
	for (int i = 0; i < S; i++) {
	tempC -= arr[i] / mid;
	tempSum += arr[i] % mid;
	}
	if (tempC <= 0) {
	l = mid + 1;
	result = tempSum + (-tempC) * mid;
	} else r = mid - 1;
	}
	bw.write(String.valueOf(result));
	bw.flush();
	}
	}

view raw Main.java hosted with ❤ by GitHub

문제

평소 요리에 관심이 많은 승균이는 치킨집을 개업하였다. 승균이네 치킨집은 파닭이 주메뉴다. 승균이는 가게를 오픈하기 전에 남부시장에 들러서 길이가 일정하지 않은 파를 여러 개 구매하였다. 승균이는 파닭의 일정한 맛을 유지하기 위해 각각의 파닭에 같은 양의 파를 넣는다. 또 파닭 맛은 파의 양에 따라 좌우된다고 생각하기 때문에 될 수 있는 한 파의 양을 최대한 많이 넣으려고 한다. (하지만 하나의 파닭에는 하나 이상의 파가 들어가면 안 된다.) 힘든 하루를 마치고 승균이는 파닭을 만들고 남은 파를 라면에 넣어 먹으려고 한다. 이때 라면에 넣을 파의 양을 구하는 프로그램을 작성하시오. 승균이네 치킨집 자는 정수만 표현되기 때문에 정수의 크기로만 자를 수 있다.

입력

첫째 줄에 승균이가 시장에서 사 온 파의 개수 S(1≤S≤1,000,000), 그리고 주문받은 파닭의 수 C(1≤C≤1,000,000)가 입력된다. 파의 개수는 항상 파닭의 수를 넘지 않는다. (S≤C) 그 후, S 줄에 걸쳐 파의 길이 L(1≤L≤1,000,000,000)이 정수로 입력된다.

출력

승균이가 라면에 넣을 파의 양을 출력한다.

예제 입력 1 

3 5
440
350
230

예제 출력 1 

145

힌트

파닭 하나당 넣을 수 있는 최대 파의 길이는 175cm으로, 440cm 파에서 2개, 350cm 파에서 2개, 230cm 파에서 1개, 총 5개의 파닭을 만들 수 있고, 각각의 파에서 90cm + 0cm + 55cm = 145cm의 파가 남는다.

출처

University > 전북대학교 > 2017 전북대학교 프로그래밍 경진대회 D번