[SWEA] 사탕 가방

       문제 요약        

- 문제

N종류의 사탕, 각 종류마다 사탕의 개수가 주어짐

 

가방 안에 정확히 M개의 사탕을 넣고,

각 가방에 들어있는 사탕 종류의 구성이 같도록 배분했을 때

최대 몇 개의 가방을 만들 수 있는가

 

- 입출력

1 <= N <= 100

1 <= M <= 10^18

1 <= Ai <= 10^18

         아이디어        

가방의 개수 : 탐색을 통해 내가 찾고자 하는 값

 

가방 N개를 만들 수 있다고 했을 때, 

가방에 종류의 구성이 같은 M개의 캔디가 들어갈 수 있는지 확인한다 

 

어떻게?

"사탕i의 개수 / M 개"로 "사탕i를 가방에 몇 개 넣을 수 있는지" 를 알 수 있다

사탕i를 가방에 넣을 수 있는 개수를 모두 더해서 M을 넘는다면 성공!

 

         소스코드        

 

package dx._16;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Solution {
	static int T; // 테스트 케이스의 수
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine()); 
		for(int testCase = 1; testCase <= T; testCase++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken()); // 사탕 종류의 개수
			long MIN_CANDY_PER_BAG = Long.parseLong(st.nextToken()); // 가방안에 M개의 사탕이 들어있어야 함
			
			st = new StringTokenizer(br.readLine());
			long max = Long.MAX_VALUE;
			long[] candy = new long[N]; // N종류마다의 사탕 갯수
			for(int i = 0; i < N ; i++) {
				candy[i] = Long.parseLong(st.nextToken());
				max = Math.max(max, candy[i]);
			}
			long bagL = 1, bagR = max;
			while(bagL <= bagR) {
				long bagCnt = bagL + (bagR- bagL) / 2;
				
				long cnt = 0; // 가방 하나에 들어가는 사탕의 개수
				for(long n : candy) { //모든 캔디에 대해 최대 몇개까지 각 가방에 넣을 수 있는지 확인
					cnt += n/bagCnt;
				}
				
				if(MIN_CANDY_PER_BAG > cnt) {
					bagR = bagCnt - 1;
				}else {
					bagL = bagCnt + 1;
				}
			}
			System.out.println("#" + testCase + " " + bagR);
		}
	}
	
}