내가 개발해볼게!!
[BOJ] 백준 2343번: 기타 레슨(Java) 본문
https://www.acmicpc.net/problem/2343
2343번: 기타 레슨
강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경
www.acmicpc.net
문제
입력
첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다.
출력
첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.
난이도
실버 1
Sol
이분 탐색을 통해 해결. 단, 강의의 순서가 바뀌면 안된다는 조건이 있기 때문에 입력받은 배열을 정렬하지 않고 그대로 사용해야 한다.
탐색 범위의 최솟값과 최댓값을 지정하는 과정에서 시행착오가 있었다..
- 블루레이 하나는 최소한 강의 하나씩은 꼭 담을 수 있는 크기여야 한다. 때문에 최솟값 left의 초기값을 가장 긴 강의의 길이로 지정했다.
- 한 블루레이에 모든 강의를 담는 경우 블루레이의 용량이 최대가 된다고 볼 수 있다. 때문에 최댓값 right의 초기값을 모든 강의의 길이의 합으로 지정했다.
최솟값과 최댓값의 중앙값 mid를 블루레이 하나의 크기라고 가정하고, 직접 강의를 배분하면서 블루레이의 개수를 체크한다. (cnt)
- 강의를 모두 나눴을 때 소모된 블루레이의 개수가 가지고 있는 블루레이 M개보다 크다면 블루레이의 용량의 최솟값(min)을 늘려서 다시 배분을 시도한다. min을 늘리기 위해 최솟값 left를 min + 1로 증가시킨다
- 강의를 모두 나눴을 때 소모된 블루레이의 개수가 가지고 있는 블루레이 M개보다 적거나 같다면, 즉 모든 조건을 충족하면서 강의 배분을 끝냈다면 그때의 블루레이의 용량 mid를 답 answer에 넣고, 가능한 블루레이의 크기 중 최소를 찾기 위해 블루레이의 용량을 줄여서 다시 배분을 시도한다. 용량 mid를 줄이기 위해 최댓값 right를 mid - 1로 감소시킨다.
최솟값 left와 최댓값 right가 반전되어 이분 탐색이 종료되면 while문을 탈출하고 최종적인 answer를 출력한다.
public class B2343_기타레슨 {
static int N, M; // 강의의 수, 블루레이의 개수
static int[] lessons; // 각 강의의 길이를 담는 배열
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer token = new StringTokenizer(bf.readLine());
int left = 0, right = 0;
int mid, cnt, sum;
int answer = 0;
N = Integer.parseInt(token.nextToken()); // 강의의 수
M = Integer.parseInt(token.nextToken()); // 블루레이의 개수
lessons = new int[N];
token = new StringTokenizer(bf.readLine());
for(int i=0; i<N; i++){
lessons[i] = Integer.parseInt(token.nextToken());
left = Integer.max(left, lessons[i]); // 한 블루레이 내에 최소한 강의 하나는 들어갈 수 있어야 한다. 즉, 가장 긴 강의 하나의 길이를 최솟값으로 잡을 수 있다.
right += lessons[i]; // 블루레이 하나에 모든 강의를 담는 경우를 최댓값 right로 볼 수 있다
}
// input
while(left <= right){ // 강의들을 블루레이 내에 직접 나눠담으면서 블루레이의 최대 용량을 찾는다
mid = (left + right) / 2; // 한 블루레이에 채울 수 있는 최대 용량
sum = 0; // 블루레이에 강의가 얼마나 차 있는지 확인하기 위한 합 변수
cnt = 1; // 블루레이의 개수
for(int i=0; i<N; i++){
sum += lessons[i]; // 블루레이에 강의를 순서대로 담는다
if(sum > mid){ // 블루레이에 강의를 최대한 채운 상황
cnt++; // 블루레이의 개수를 늘리고
sum = lessons[i]; // 해당 강의를 새 블루레이에 담기 시작한다
}
} // 모든 강의를 블루레이에 나눠 담고, 블루레이 개수가 유효한지 체크한다
if(cnt > M) left = mid + 1; // 만약 주어진 블루레이의 개수보다 블루레이가 더 필요하다면 한 블루레이에 채울 수 있는 최대 용량을 늘리기 위해 용량의 최솟값을 수정한다
else {
right = mid - 1; // 만약 주어진 블루레이의 개수 내에서 강의를 배분할 수 있다면 블루레이의 최소 크기를 찾기 위해 용량을 줄인다. 즉, 용량의 최댓값을 수정한다
answer = mid; // 블루레이 하나의 최대 용량을 답으로 지정
}
}
// operation
System.out.println(answer);
// output
}
}
'Algorithm > BOJ' 카테고리의 다른 글
[BOJ] 백준 11403번: 경로 찾기(Java) (0) | 2023.08.25 |
---|---|
[BOJ] 백준 20055번: 컨베이어 벨트 위의 로봇 (0) | 2023.08.23 |
[BOJ] 1012번: 유기농 배추 (0) | 2023.08.15 |
[BOJ] 1932번: 정수 삼각형(Java) (0) | 2023.08.10 |
[BOJ] 9465번: 스티커 (0) | 2023.08.08 |