🪕 기타 레슨

https://www.acmicpc.net/problem/2343

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	11533	3679	2620	30.412%

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

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

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

입력

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

출력

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

예제 입력 1

9 3
1 2 3 4 5 6 7 8 9

예제 출력 1

17

힌트

강의는 총 9개이고, 블루레이는 총 3개 가지고 있다.
1번 블루레이에 1, 2, 3, 4, 5, 2번 블루레이에 6, 7, 3번 블루레이에 8, 9 를 넣으면 각 블루레이의 크기는 15, 13, 17이 된다. 블루레이의 크기는 모두 같아야 하기 때문에, 블루레이의 크기는 17이 된다. 17보다 더 작은 크기를 가지는 블루레이를 만들 수 없다.

🙄 Parametric Search

Parametric Search 이란 최적화 문제(문제의 상황을 만족하는 특정 변수의 최소 혹은 최댓값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것이다. - 종만북
예를 들어, 수 많은 사람들 중에서 가장 어린 면허 조시자를 찾고자 한다고 생각해보자.

• 수 많은 사람들 중에서 가장 어린 면허 소지자는 누구인가?
• 단, 면허 소지자는 나이가 19세 이상이라는 가정을 덧붙이겠다.
  ( 최적화 문제)

해당 문제를 해결하기 위해서는 어떻게 해야할까?
N명의 사람이 있다고 해보자.
이들은 나이에 상관없이 배열되어 있을 것이다.
그러면, 우리는 가장 처음 사람부터 마지막 사람까지 하나하나 확인해보면서 최연소 면허소지자를 찾을 수 밖에 없다. O(N)

그러면, 만약에 이들이 나이순으로 정렬되어있다고 해보자.
그럼에도, 우리는 처음 사람부터 마지막 사람까지 확인을 해봐야 하므로 최악의 시간 복잡도가 O(N)임은 변함이 없다.
질문을 바꿔보자.

• 당신은 면허가 있나요?

이제 최적화문제를 결정문제로 바꾸었다.
이 질문으로 주어진 문제 상황을 해결할 수 있는지 살펴보자.

" 당신은 면허가 있나요? " 라는 질문을 ' 나이 ' 라는 기준에 맞추어 정답을 해결할 것이다. 그러면, 나이의 상한과 하한을 정해서 각각 right, left 라고 해주자.
left 는 어떤 값으로 설정할까?
0으로 설정하면 문제가 없겠지만, 만일 N명의 사람들 중 가장 어린 나이를 left로 설정하는 것이 보다 좋을 것이다.
마찬가지로 right 를 1e6과 같은 수로 해도 좋겠지만, 만일 N명의 사람들 중 최연장자의 나이를 설정할 수 있는게 보다 효율적일 것이다.
상한과 하한을 설정했는데, 그러면 어떤 사람에게 먼저 면허가 있냐고 여쭤보는게 좋을까?
상한과 하한의 중간에 위치한 사람에게 먼저 질문을 하는 것이 바람직할 것이다.

target = (left+right)/2

만약 그 사람이 면허가 없다라고 하면?
그러면, 그 사람의 index 이하의 사람은 정답 범위에서 벗어난다. 그들은 19세 미만 학생들일 것이고, 면허가 없는게 확실하기 때문이다. 그러면 target을 어떻게 갱신하면 좋을까? 우리가 방금 여쭤보았던 사람의 바로 다음부터 가장 끝 사람 중 가운데를 찾아보는 것이 합리적이다.

left = target+1
target = (left+right)/2

새로 질문을 했는데, 그 사람이 바로 면허 소지자이다. 그러면, 해당 사람의 다음 번호부터 끝까지는 당연히 정답 범주에서 제외된다. 왜냐면 우리는 최연소 면허 소지자를 찾고 있으니까! 방금 여쭤봤던 사람의 이름을 우리는 쪽지에 기록해둔 다음, 탐색을 진행하자.

right = target-1
target = (left+target)/2

위와 같이 갱신을 하면, 방금 여쭤보았던 사람의 바로 앞 번호가 상한이 된다.
새로 정한 target 이 면허 소지자가 맞다면, 우리가 가지고 있던 쪽지를 버리고 그 사람의 이름을 새로운 쪽지에 기록하면 된다. 위와 같은 과정을 반복하면, 결국 쪽지에는 최연소 면허 소지자의 이름만 남게 된다. ~> 이 경우 left 값에 저장된 값이 결국 우리가 원하는 것!

• 최적화 문제를 결정 문제로 바꾸었을 때 무엇이 달라졌을까?

1. 최적화 문제일 때에는 N명의 사람들에게 물어봐야 하므로, 최악의 경우 N번의 사람을 만나야한다. ( 시간 복잡도 : O(N) )
2. 결정 문제로 바꾸었을 때에는, 탐색을 진행할 수록 찾아야 하는 데이터 수가 절반씩 줄어든다.
   -> 🙄이거 이진탐색 아니냐?
   😮그리고 최적화 문제 방식은 순차 탐색인 것 같은데?
   

• 맞다. 결정 문제로 바꾸면 이진 탐색으로 해결하는 것과 같다.
  이진 탐색은 시행할 수록 남은 데이터가 절반 씩 줄어들기 때문에, K 번 시행 후에는 N(1/2)^K 개의 데이터가 남게 될 것이고, 탐색이 끝나면 당연히 1개의 데이터만 남는다.

  N(1/2)^K ~= 1
  양변에 2^K를 곱해주면,
  2^K = N
  양변에 2를 밑으로 하는 로그를 취해주면,
  K = log2N
  여기서 K는 시행 횟수였다.
  즉, 데이터가 N개일 때 우리는 log2N 번의 시행 횟수가 보장된다.
  고로, Big O 표기법에 의하면 O(logN) 으로 나타낼 수 있다.

😎 문제 적용

위, 기타 레슨의 경우 전형적인 Parametric Search 문제이다.

• N개의 강의 수와 담아야할 블루레이 수 M을 입력으로 받는다.
• 더불어 각 강의의 러닝타임을 분 단위로 받는다.
  -> 🙄배열로 받아야겠다.
• 블루레이 크기 중 가장 최소를 출력하라고 한다.
• 각 강의의 러닝타임이 1 2 3 4 5 6 7 8 9 라고 하고 블루레이 수를 3이라고 했을때, 1+2+3+4+5 // 6+7 // 8+9 와 같이 담는 것이 최적의 방법이고 이를 위해서 블루레이의 분수는 최소 8+9 = 17분이여야 한다.
• 최적의 블루레이 크기를 묻는 최적화 문제이다.
• Parametric Search 를 적용하여 문제를 풀 수 있겠다.
• 근데, "레슨의 순서가 바뀌면 안된다." 라는 조건이 있으니까 정렬은 하지 않는다! 😥 이 조건을 놓쳐서, 정렬을 자꾸 시키는 바람에 자꾸 틀렸었다..
• 가능한 블루레이 길이의 하한, 상한을 정해놓고, (하한+상한)/2 를 블루레이 길이로 설정했을 때 블루레이를 총 몇 개 사용해야 하는지 개수를 센다. 그리고 그 개수 count 와 M을 비교하면서 상한과 하한을 조정해준다.
• count > m 인 경우에는, 기존에 사용하고자 하는 블루레이 개수보다 더 많이 쪼갠 경우니까, 블루레이 길이를 줄여야 하므로 하한을 올려준다.
• count 를 계속 갱신해야할 텐데, count는 아래와 같이 구해준다.

    int sum = 0; // 초기값
    int count = 0; //초기값
    for(int i = 0 ; i < arr.size(); i++) //배열 원소 전체에 대해서
    {
      if(sum+arr[i]>mid) // sum을 갱신하다가, mid 값보다 커질 것 같으면
      {
        sum = 0; // sum 을 0으로 초기화하고
        count ++; // 블루레이를 쪼갤 거니까 count 를 하나 늘린다.
      }
      sum += arr[i]; // 원소 합을 sum에 저장하는데
    } // 이 루프가 끝났을 때 sum = 0 이면 딱 떨어진 거이므로 count 를 더 높이거나 하지 않아도 된다.
    if(sum != 0) count ++;
    // 근데 만약에 sum 이 0이 아니다? 그러면 강의 분 수가 좀 남는거니까 이를 담을 
    블루레이 하나 더 추가.

• 이진 탐색 부분은 아래와 같다.

int sol(vector<int>& arr, int m ) // m 은 원하는 블루레이 개수
{
  int left = 0; // 하한 초기값
  for(int i = 0 ; i < arr.size(); i ++)
  {
    if(left<arr[i]) left = arr[i]; //블루레이 길이는 
    최소 가지고 있는 강의의 최대 러닝타임이 되야할 것.
  }
  int right = 0 ; // 상한 초기값
  for(int i = 0 ; i < arr.size(); i ++)
  {
    right += arr[i];
  }
  // 블루레이 길이가 최대가 되는 경우는, 각 강의 러닝타임의 합

while(left<=right) // 이진 탐색시작
  {
    int mid = (left+right)/2; // 상한+하한 의 절반으로 블루레이 길이를 정한다면?
    int sum = 0; 
    int count = 0;
    for(int i = 0 ; i < arr.size(); i++)
    {
      if(sum+arr[i]>mid)
      {
        sum = 0;
        count ++;
      }
      sum += arr[i];
    }
    if(sum != 0) count ++;
// 필요한 블루레이 개수 count 계산

    if(count > m ) // count 와 m 을 비교
      left = mid + 1; // 갱신
    else 
      {
        right = mid - 1; // 갱신
      }
  }
  return left; //최소값을 원하므로 left 가 답
	

😊 전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int sol(vector<int>& arr, int m )
{
  int left = 0;
  for(int i = 0 ; i < arr.size(); i ++)
  {
    if(left<arr[i]) left = arr[i];
  }
  int right = 0 ;
  for(int i = 0 ; i < arr.size(); i ++)
  {
    right += arr[i];
  }


  while(left<=right)
  {
    int mid = (left+right)/2;
    int sum = 0;
    int count = 0;
    for(int i = 0 ; i < arr.size(); i++)
    {
      if(sum+arr[i]>mid)
      {
        sum = 0;
        count ++;
      }
      sum += arr[i];
    }
    if(sum != 0) count ++;

    if(count > m )
      left = mid + 1;
    else
      {
        right = mid - 1;
      }
  }
  return left;

}

int main()
{
  vector<int> arr ;
  int n, m;
  cin >> n >> m ;
  int input;
  for(int i = 0 ; i < n;i++)
  {
    cin >> input;
    arr.push_back(input);
  }

  cout << sol(arr,m);

  return 0;
}

🤔 What if?

if(count > m )
  left = mid + 1;
else
  {
    right = mid - 1;
  }

  위 코드를 아래와 같이 바꿔보자.
  

if(count < m )
right = mid - 1;
else
{
left = right + 1;
}

아래와 같이 코드를 짜면 오답 처리를 받는다.
왜그런걸까? 하나하나 뜯어보자...

• if(count < m ) 라는 것은 mid 값으로 블루레이 길이를 맞추었을 때 블루레이 조각 수가 원하는 블루레이 조각 수보다 적은 것이다.
• 그러면 조각 수를 늘려야 하므로, 길이를 줄여야 한다.
• else -> count 가 m 보다 크다는 것으로 조각 수를 줄여야 하므로 길이를 늘려야 한다. 하지만 count == m 인 경우도 여기에 속하게 되고, 길이를 늘리게 된다.
• count == m 인데 길이를 늘린다...?
• 우리는 선택할 수 있는 블루레이 길이 중 최소를 찾고자 하는데, 조건에 맞는데 왜 길이를 늘리고 있을까😂
• count == m 이면 길이를 줄여야 맞다.
• 그러니까 if (count < m ) 이 아니라 if (count <= m) 이 되어야 한다.