백준2343(기타레슨)

jh Seo·2022년 9월 26일

백준 이분탐색 한번에 못 푼 문제

백준

목록 보기

44/180

개요

백준 2343번: 기타 레슨

입력
첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다.
출력
첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.

접근 방법

처음 떠올린 방식은 그냥 입력값을 다 더하고 3으로 나누면 세부분으로 나뉘는 값 중 최소값이 나오지 않나 생각했었다.
-> 예제를 본 후, 연속된 부분을 잘라야 한다는걸 깨달았다.
그 후 단순히 중간값인 mid를 기반으로 나눈 후
나뉜 범위의 값들의 합 중의 최대값을 return하게 maxPartialSize(int mid)함수를 짜봤는데
처음에 입력받은 M만큼만 나뉘어야한다.

코드

#include<iostream>

using namespace std;
int N, M,Sum=0;
int inputArr[100'001];

//입력값 구하는 함수
void input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> inputArr[i];
		Sum += inputArr[i];
	}
	
}

//그냥 단순히 들어온값보다 작을때까지 더해서 해당 합의 최댓값을 return하려했는데 들어온값보다 작은 범위까지 다 더하는 과정에서 ret이 m개 생기는지 체크해야함.
/// <summary>
/// medium값으로 넘어온 값을 기준으로 범위를 나누고 범위가 M개로 나눠지지 않으면 false, 나뉘면 true return하는 함수
/// </summary>
/// <param name="medium"></param>
/// <returns></returns>
bool maxPartialSize(int medium) {
	//각 부분들의 합 , 몇군데로 나눠야할지 
	int partialSum=0,partiallimit=M;
	//0부터 N까지
	for (int i = 0; i < N; i++) {
		//만약 medium보다 큰 원소있다면 불가능
		if (inputArr[i] > medium) return false;
		//각 부분합 구하기
		partialSum += inputArr[i];
		//i번째 원소 더했을때 medium값 넘겼을 때
		if (partialSum > medium) {
			//partiallimit하나 지우고 한 부분 완성
			partiallimit--;
			//지웠을 때 0인 된다면 M번보다 더 많이 나누게 되는것이므로 불가능 
			if (partiallimit <= 0) return false;
			//partialSum은 i번째 반복을 이미 한 값이므로 i번째 원소값만 냅둠
			partialSum = inputArr[i];
		}
	}
	return true;

}

//그냥 다더하고 3으로 나누면 15가되어서 왜 17일까하다가 문제 다시보니 연속된거로 끊어야하네
void solution() {
	//Sum을 M개로 나눈 게 최소
	int mid = 0, low = 0, high = Sum;
	//low와 high가 1차이 날때까지
	while (low + 1 < high) {
		mid = (low + high) / 2;
        //mid값을 기준으로 M개의 범위가 나뉘면 high값에 mid값 넣고, 
        //M개보다 더 많이 나뉘면 low를 높여서 mid값을 더 올린다.
		((maxPartialSize(mid)) ? high : low) = (low + high) / 2;
	}
    //최소값이므로 high값이 답이 되는 최소값, low값에 답이 안되는 마지노선 값이 들어간다.
	cout << high;
}

int main() {
	input();
	solution();
}