[Silver I] 기타 레슨 - 2343Permalink

문제 링크

성능 요약Permalink

메모리: 1504 KB, 시간: 16 ms

분류Permalink

이분 탐색, 매개 변수 탐색

제출 일자Permalink

2023년 12월 26일 21:40:10

문제 설명Permalink

강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.

강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.

강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

입력Permalink

첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다.

출력Permalink

첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.

TILPermalink

• 알고리즘이 맞았다면 문제는 자료형, or 무한루프
  (이 문제의 경우에는 블루레이 크기가 작아서 강의 하나도 제대로 못 담을 경우의 예외처리)

FeedBackPermalink

• 블루레이 크기가 작아서 강의 하나도 제대로 못 담을 경우의 예외처리를 추가로 해주어야 한다. 다행히 이 경우를 스스로 찾았다. (동일한 구조의 문제를 푼경험이 있기에) 동일한 구조를 가진 문제 (용돈 관리)

내 접근Permalink

parametric search가 이제 익숙해져서 정말 쉽게 풀었다.
다만 상술한 예외처리를 안해서 틀려서 자료형이 문제인가? 생각하보았고, long long형으로 바꾸어도 보았다.
하지만 문제의 조건내에서 int형의 표현범위를 벗어나는 케이스는 나올수 없어 의아했고, 오버플로우가 문제가 아님을 깨달았다.
답은 추가적인 예외 조건(원소를 하나도 담지 못할 경우는 바로 실패 판정)을 해주는 것이였다.
명쾌하게 답을 내 스스로 구한 문제여서 기분이 좋다.
실력이 상승하는 것이 느껴진다.

내 코드Permalink

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//Time Complexity : O(nlogn)

int main() {

	//input
	int n, limit;
	scanf("%d %d", &n, &limit);
	int* lectures = (int*)malloc(sizeof(int) * n);
	for (size_t i = 0; i < n; i++)
		scanf("%d", &lectures[i]);
	int low = 1, high=0;
	for (size_t i= 0; i < n; i++) {
		high += lectures[i];
	}


	
	while (low <= high) {
		int usedBlurays = 0; //소비된 블루레이 개수
		int mid = low + (high - low) / 2;

		//블루레이 기록하기 
		int remainingSpace = 0;
		bool isEnough = true;
		for (size_t i = 0; i <n; i++) {
			if (lectures[i] > mid) {
				isEnough = false;
				break;
			}
			if (lectures[i] > remainingSpace) {
				usedBlurays++;
				remainingSpace = mid;
			}
			remainingSpace -= lectures[i];
		}
		
		if (usedBlurays > limit||!isEnough) low = mid + 1;
		else high = mid - 1;
	}
	
	printf("%d", low);

	free(lectures);
	return 0;
}

굳!