[백준 14627 / 파닭 파닭 / JAVA / 이분 탐색]

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

14627번: 파닭파닭

 

문제 접근

 

파 길이 배열로 만들어서 입력

저장된 파 길이들을 현재 파 길이(mid)로 나눠서 치킨 몇 마리(count) 만들 수 있는지 검사

count가 만들어야 하는 치킨 수(C)보다 크거나 같으면 더 긴 파 길이를 탐색하기 위해 left를 당기고 그 때의 파 길이(mid)를 저장

치킨 수 보다 작다면 파 길이를 줄여서 원하는 치킨 수를 충족하기 위해 right를 당기기

이 작업 반복

 

마지막에 남는 파 길이를 계산하기 위해 

모든 파 길이 - (자를 수 있는 최대 파 길이 * 만들어야 하는 치킨 수)를 계산해준다.

→ long answer = sum - (result * C);

 

++ 처음에 남는 파 길이 계산할 때

for(int i=0; i<S; i++) {
   sum += (chicken[i] % result);
 }

이렇게 sum에다가 저장된 파 길이들을 하나씩 최대 파 길이로 나눈 나머지들을 다 저장해서 출력했었다.

이렇게 해도 입력 예제와 내가 따로 입력한 값들의 결과는 동일했는데 정답은 아니더라

둘 계산에 무슨 차이가 있는거지?

이해가 안된다.

 

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

public class Main {
	public static void main(String[] args) throws IOException {
	   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   StringTokenizer st = new StringTokenizer(br.readLine());
	   
	   int S = Integer.parseInt(st.nextToken()); // 파의 개수
	   int C = Integer.parseInt(st.nextToken()); // 주문 받은 파닭 수
	   
	   int[] chicken = new int[S];
	   
	   for(int i=0; i<S; i++) chicken[i] = Integer.parseInt(br.readLine());
        
	   long left = 1;
	   long right = 1000000000;
	   long result = 0;
	   long sum = 0;
	   
	   while(left <= right) {
		   long mid = (left + right) / 2;
		   
		   int count = 0; // 현재 파 길이(mid)로 만들 수 있는 파닭 수
		   for(int i=0; i<chicken.length; i++) {
			   count += chicken[i] / mid; 
		   }
		      if(count >= C) {
			   result = mid;
			   left = mid + 1;
		   }
		
		   else if(count < C) {
			   right = mid - 1;
		   }
	   }
	   
	   for(int n : chicken) sum += n;
	   long answer = sum - (result * C);
	   System.out.println(answer);
	   
	}
}