13702 이상한 술집
1. 문제 풀이
이분탐색으로 풀면 된다.
코드를 설명하겠다.
1) 예제
문제에 나온 예제를 살펴보자.
2 3
702
429
2) 변수 설명
N(주문한 막걸리 주전자 개수) : 2,
K(친구들의 수) : 3
주전자 용량 : 702, 429 => drink 배열에 입력
이분탐색에 필요한 변수
left = 0, right = 702 (주전자 용량 중 제일 큰 값) => mid = (0+702)/2 = 351
이분탐색을 시작한다.
for(int i=0; i<N; i++) {
count+=drink[i]/mid;
}위의 코드에서 볼 수 있듯이,
count 변수는 각각의 주전자 용량을 mid 값으로 나눈 값 중 정수부분의 합이다.
count 변수가 int 형 이므로 소수점은 버려지고 정수만 더해진다.
즉, 맨 처음에 mid = 351 인데,
1) 주전자 용량 : drink[0] = 702
=> 702/351 = 2
=> count = 2
즉, 하나의 주전자에 들어있는 702 ml 막걸리를 351ml씩 나눠주면 2번 나눠줄 수 있다.
2) 주전자 용량 : drink[1] = 429
=> 429/351 = 1.22222
=> count = 3 (1.22222.......... 이지만 정수만 더해짐)
우리는 최종적으로, count = K 를 만족시키는 최대 막걸리 용량을 이분탐색으로 찾으면 된다.
3) 이분탐색
그러면 이제 제대로 이분탐색을 해보자.
1) left = 0, right = 702, mid = 351 // 위에서 설명함
=>
702/351 = 2,
429/351 = 1.22
최종 count = 3
현재 count = 3 = K 를 만족하지만, 문제에서 최대 막걸리 용량을 출력하라고 했다.
count = 3 을 만족하는 더 많은 막걸리 용량이 있을 수 있다.
그래서 이분탐색이 이어진다.
left, right, mid가 막걸리 용량을 의미하는데,
left 변수 값을 증가시키거나, right 변수 값을 줄이는 두가지 경우가 있다.
if(count >= K) {
left = mid+1;
}else{
right = mid-1;
}
여기서는
용량이 늘어나는 쪽, left = mid +1 로 가야 된다.
=> left = 352
2) left = 352, right = 702, mid = 527
이때는 count = 1 이 된다.
그러면, count = 3이 만족되게 하려면,
count = ('drink[0]/ mid' 정수부분) + ('drink[1]/ mid' 정수부분)
이므로, mid 를 줄여야 한다.
그러려면 right = mid-1 쪽으로 간다.
3) left = 352, right = 526, mid = 439
이때도 count =1 이 된다.
이런 작업을 반복하다가,
8번째가 되면,
8) left = 352, right = 355, mid = 353
이때도 count =2 이다.
9) left = 352, right = 352, mid = 352
이때도 count =2 가 된다.
그러면 right = mid -1 이 되는데, 이때 right = 351 이 된다.
그러면 while 문의 조건인 left <= right 조건이 만족이 안돼서
while 문을 탈출한다.
그리고 최종적으로 right = 351 을 답으로 출력한다.
2. 헷갈렸던 부분
내가 고민했던 부분이 이 부분이다.
1) 정답이 mid 라고 생각했던 이유
나는 right 가 아닌 mid가 우리가 찾는 정답, 즉 최대 막걸리 용량을 나타낸다고 생각했다.
for(int i=0; i<N; i++) {
count+=drink[i]/mid;
}count 값은 위와 같이 구해진다.
위에 설명했듯이, 이분탐색 맨 처음에
left = 0, right = 702, mid = 351, drink[0] = 702, drink[1]= 429 이다.
mid = 351 인 막걸리 용량만큼
drink[0] = 702 인 주전자 용량을 나누면 (702/351 =2)
2명에게 나눠줄 수 있고,
drink[1] = 429 인 주전자 용량을 나누면 (429/351 = 1.2222)
1명에게 나눠줄 수 있다.
따라서 총 3명의 친구에게 나눠줄 수 있고, 이는 K(친구 수) = 3 과 같다.
문제에서 정답으로 K명에게 나눠줄 수 있는 최대 막걸리 용량을 출력하라고 했다.
그래서 나는 mid = 351만큼씩 나눠주면 3명에게 나눠줄 수 있듯이,
count = K를 만족하는 최대 mid 값을 정답으로 제출해야 된다고 생각했다.
주전자 용량(drink[i])을 right 가 아니라 mid 로 나누기 때문이다.
그런데 right 가 답이다.
왜 그런지 그림으로 살펴보겠다.
2) 정답이 right 인 이유
위에서 계속 설명한 아래 예제에 대한 설명이다.
2 3
702
429
풀이 과정은 위에서 설명했으므로 간단하게 설명하며 넘어가겠다.
그림에 mid 값을 나타내 보았다.
(첫 번째, 두 번째, 여덟 번째, 아홉 번째 mid 값을 나타낸 것이다.
맨 처음 mid = 351 에서 두번째 527이 된 후에는 계속 mid 값이 줄어들어서 화살표로 줄어듦을 표현했다.)
1) 맨 처음 left = 0, right = 702, mid = 351 이다.
이때 count = 3 으로 K와 같다.
그런데, count = 3 을 만족하는 더 큰 막걸리 용량을 찾기 위해 mid 값을 527로 증가시켰다.
2) left = 352, right = 702, mid = 527
=> count = 1
// K = 3과 같지 않다.
3) mid = 439
=> count = 1
4) mid = 395
=> count = 2
...
8) mid = 353
=> count = 2
9) mid = 352
=> count = 2
10) 이때는 left = 352, right = 351 이다.
left> right 가 되어서
while 문을 탈출한다.
즉, 맨 처음 mid = 351 일때 count = 3 으로 K 와 일치했지만,
더 큰 막걸리 용량을 찾기 위해 mid 값을 증가시켰다.
그런데, count =1 이 되어, mid값을 점점 줄여야 했고,
줄이다 줄이다, mid = 352 가 되었을 때도 count =2 가 되어서
count = 3을 만족하지 못하게 된 것이다.
결국 맨 처음 mid = 351 일때가 count = 3을 만족하는 최대의 값이였던 것이다.
그런데 첫 번째
left = 0, right = 702, mid = 351 이후
left = mid +1 = 352 가 되어서, 9번째까지 left = 352가 된다.
우리가 원하는 정답은 351이고, right 가 left 보다 작아진 그 때, 즉 351이 되었을 때 while문을 탈출하고
이 값을 최종 답으로 제출하는 것이다.
그래서 right 가 답이 된다.
3. 최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
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 N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
long drink [] = new long [N];
long right = 0;
for(int i=0; i<N; i++) {
drink[i] =Integer.parseInt(br.readLine());
right = Math.max(drink[i], right);
}
long left = 0;
long mid = 0;
while(left <= right) {
int count = 0;
mid = (left + right)/2;
if(mid == 0) {
break;
}
for(int i=0; i<N; i++) {
count+=drink[i]/mid;
}
if(count >= K) {
left = mid+1;
}else{
right = mid-1;
}
}
System.out.println(right);
}
}
참고 블로그 :
https://ddb8036631.github.io/boj/13702_%EC%9D%B4%EC%83%81%ED%95%9C-%EC%88%A0%EC%A7%91/
[백준] 13702. 이상한 술집
문제 링크
ddb8036631.github.io