문제 탐색하기
입력 자료 정리
- n은 막걸리 주전자의 개수이며, k는 막걸리를 마실 사람의 수이다
- 이어서 들어오는 n번의 입력값은 각 주전자의 막걸리 용량이다
해결방법 추론
- 처음에는 문제를 읽고나서는 그리디를 떠올렸다.
가장 크거나 가장 작은 용량, 혹은 그 이외의 방법으로 그리디하게 분배할 수 있는 용량을
구하면 문제를 해결할 수 있겠다고 생각하였다 - 하지만 입력/출력을 보고 문제를 다시 읽었을 때, 생각이 바뀌었다
그리디 알고리즘으로는 그리디하게 분배하는 방법을 떠올리기 쉽지 않았고,
오히려 주어진 막걸리 용량 범위내에서 가장 적합하게 분배할 수 있는 용량을
값을 조절해가면서 탐색한다면 해결할 수 있겠다고 생각하였다 - 하지만 막걸리의 최대 용량은 2^31 - 1이다. 따라서 이분탐색으로 범위를 탐색해야 한다
- 최소는 1, 입력 막걸리의 최대 용량으로 하고, 중간지점을 기준으로 원소값들을 나눴을 때,
그 몫들의 합을 k와 비교하여, 가장 적합하게 k명에게 제공할 수 있는 지점을 찾는다
시간복잡도 계산
- 시간복잡도를 계산하기 전에 먼저 막걸리의 최대 용량을 m이라 하겠다.
- 이때 이분탐색에서 n만큼 순회하면서 모든 배열의 값을 비교하여 count를 셀 것이므로
n만큼의 연산이 발생한다 - 이어서 이분탐색의 대상은 막걸리의 최대 용량이다.
따라서 막걸리의 용량인 m을 이분탐색했을 때의 최대연산은 logm이 된다 - 시간복잡도는 O(n x logm)이 되며 시간제한안에 문제를 해결할 수 있다
코드 설계하기
입력값 상태 관리하기
- 들어오는 n과 k는 int형 변수로 관리한다
- 이어서 left와 right를 초기화한다.
left는 1로 초기화하며, right는 0으로 초기화해준다 - n만큼 순회하면서 int형 타입의 1차원 배열에 입력값들을 넣어준다
- 이어서 right에는 right와 원소값을 비교하여 더 큰 값을 넣어준다
- 정답을 위한 ans를 최댓값을 찾기 위해 0으로 초기화해둔다
- 이때 left,right, ans를 모두 long타입으로 선언하는데,
이후 이분탐색에서 mid값이 int형 범위를 벗어날 수 있기 때문이다. - 2^31-1이 막걸리의 최대 용량이 될 수 있으며, right가 2^31-1이 된다면
left가 조금만 커져도 int형 범위를 벗어나기 때문이다
이분탐색 설계
- left가 right보다 작거나 같은동안 탐색을 반복한다
- 분배가능한 인원수를 체크할 long타입의 count 변수를 0으로 초기화하여 하나 선언한다
- n만큼 탐색하면서 원소를 mid로 나눈 몫을 count에 더해준다
- count와 k를 비교하여 작은 경우 정답을 만족시키지 못하므로
right범위를 조정한다 - 그 외의 경우는 정답을 만족시키며 최적의 값을 찾기 위해 left의 범위를 조정하고
ans에는 mid와 비교하여 더 큰값을 넣어준다
출력값 설계
- 완성한 ans를 출력하면 정답이 된다.
정답 코드
(1회차 시도 성공!)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int[] arr = new int[n];
long left = 1;
long right = 0;
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
right = Math.max(right, arr[i]);
}
long ans = 0;
while(left <= right){
long mid = (left + right) / 2;
long count = 0;
for (int i = 0; i < n; i++) {
count += arr[i] / mid;
}
if(count < k){
right = mid - 1;
}else{
left = mid + 1;
ans = Math.max(ans, mid);
}
}
bw.write(ans+"");
br.close();
bw.close();
}
}문제 링크
Software Developer