728x90
반응형
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Main {
public static int n;
public static int m;
public static int arr[];
public static void main(String args[]) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st=new StringTokenizer(br.readLine());
n=Integer.parseInt(st.nextToken());
m=Integer.parseInt(st.nextToken());
arr=new int[n];
int start=0;
int end=0;
for(int i=0;i<n;i++){
arr[i]=Integer.parseInt(br.readLine());
end+=arr[i];
if(start<arr[i]){
start=arr[i];
}
}
while(start<=end){
int mid=(start+end)/2;
int sum=0;
int cnt=0;
for(int i=0;i<n;i++){
if(sum+arr[i]>mid){
cnt++;
sum=0;
}
sum+=arr[i]; //집어넣고 다시 k원 인출 가능
}
if(sum!=0){
cnt++;
}
if(cnt>m){
start=mid+1;
}else{
end=mid-1;
}
}
System.out.println(start);
}
}
|
cs |
start와 end의 기준을 잘 세워줘야 했다.
나는 start를 1 end를 100000으로 해줬는데 생각해보니 end의 경우 하나 당 들어올 수 있는 최대가 10000였다. 그래서 end는 원소의 총합으로 해줘도 좋고, 아예 1000*100000(n값의 최대)로 설정해줘도 된다.
그러면 문제는 start이다. start를 찾아내기 위해서는 이진탐색의 mid가 무엇을 의미하는지 다시 생각해볼 필요가 있다. mid는 결국에 현우가 인출할 금액이고, 이 금액은 하루 동안 쓸 금액보다 많으면 많았지 적어서는 안된다.
이런 상황을 예방하기 위해서 start를 잘 설정해줘야 한다. 결국에 하루동안 쓸 금액의 기준은 n개의 수들 중 가장 큰 수를 기준으로 두면 인출할 금액이 하루동안 쓸 금액보다 많거나 같게 된다.
start는 n개의 수 중 가장 큰 수 end는 n개의 수를 다 더한것 이라 생각하면 될 것 같다.
728x90
반응형
'알고리즘 > 이진탐색' 카테고리의 다른 글
| [java백준] 실버 1/ 2343번 기타레슨 (0) | 2022.07.26 |
|---|---|
| [C++ 백준] 실버 4/ 1920번 수찾기 (0) | 2022.02.08 |
| [java 백준] 골드 5/ 2110번 공유기 설치 (0) | 2022.01.26 |
| [java 백준] 실버 4/10816번 숫자카드 2 (0) | 2022.01.26 |
| [java 백준] 실버 4/10815번 숫자카드 (0) | 2022.01.24 |
댓글