728x90
https://www.acmicpc.net/problem/17951
17951번: 흩날리는 시험지 속에서 내 평점이 느껴진거야
시험지를 12, 7, 19, 20과 17, 14, 9, 10 으로 나누면 맞은 문제 개수의 합의 최소는 50이다.
www.acmicpc.net
728x90
메모리: 22,880 KB , 시간: 288 ms
사용 알고리즘: 이분 탐색, 매개 변수 탐색
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[] arr = new int[N];
int sum = 0;
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
sum += arr[i];
}
// 이분 탐색
int s = 0, e = sum, m;
int count;
int result = 0;
while(s <= e) {
m = (s + e) / 2;
// 합이 m 이상이도록 그룹을 나눴을 때, 그룹의 개수가 K개인지 확인
sum = 0; count = 0;
for (int i = 0; i < N; i++) {
sum += arr[i];
if(sum >= m) {
sum = 0;
count++;
}
}
if(count >= K) {
result = m;
s = m + 1;
} else e = m - 1;
}
System.out.println(result);
}
}
728x90
'Programming Language > Java' 카테고리의 다른 글
명품 JAVA Programming 제6강 자바 기본 프로그래밍 실습문제 (0) | 2020.08.22 |
---|---|
명품 JAVA Programming 제5강 자바 기본 프로그래밍 실습문제 (0) | 2020.08.08 |
명품 JAVA Programming 제4강 자바 기본 프로그래밍 실습문제 (0) | 2020.08.07 |
명품 JAVA Programming 제3강 자바 기본 프로그래밍 실습문제 (0) | 2020.07.22 |
명품 JAVA Programming 제2강 자바 기본 프로그래밍 실습문제 (0) | 2020.07.15 |